带油耗的单商品取送货旅行商问题研究-数学、应用数学专业论文.docxVIP

万方数据 万方数据 摘 要 单商品取送货旅行商问题（1-PDTSP）是传统旅行商问题（TSP）的一类新 变种,本文研究的是带油耗的单商品取送货的旅行商问题，目标为使车辆在完成 所有任务之后所使用的燃油费用和车辆违反时间窗的惩罚费用之和最小。 本文共分为四章，主要研究了两个带油耗的单商品取送货旅行商问题：第 一章介绍了1-PDTSP的研究现状和本文问题的研究意义，并且介绍了本文的主要 内容；第二章对1-PDTSP以及本文需要用到的算法进行了介绍，同时讨论了 1-PDTSP与带油耗的1-PDTSP不同之处；第三章研究了带油耗的单商品取送货旅 行商问题，建立了该问题的非线性混合整数规划模型，并且给出了求解它的一个 贪婪式启发式算法和一个遗传算法，给出一个例子对算法进行了说明；第四章研 究了软时间窗下带油耗的单商品取送货旅行商问题，该问题是在第三章问题的基 础上对每个客户点都给出了一个时间窗约束，改进了第三章提供的贪婪式启发式 算法对其进行求解，给出了一个例子对算法进行说明。 关键词：单商品旅行商问题,油耗,时间窗,贪婪式启发式算法，遗传算法 Study on One-commodity Pickup and Delivery Traveling Salesman Problems with Fuel Consumption Abstract The one-commodity pickup and delivery traveling salesman problem is a new class of variants of the traditional Traveling Salesman Problem (TSP), this paper research the one-commodity pickup and delivery traveling salesman problems with duel consumption, aiming at minimizing the sum of the costs about the fuel consumption and the punishment costs of the vehicle violating the time window after it finishes all the tasks. This paper is divided into four chapters, it mainly discusses two 1-PDTSP with duel consumption. Chapter 1 describes the research status of the 1-PDTSP, the significance of the studies in this paper, and introduces the main contents of this paper. Chapter 2 presents the 1-PDTSP and some algorithms used in this paper. Chapter 3 studies a 1-PDTSP with fuel consumption, builds its nonlinear mixed integer programming model, and proposes a greedy heuristic algorithm and a genetic algorithm to solve it, an example is given to illustrate the algorithm. Chapter 4 studies a 1-PDTSP with duel consumption and soft time windows, this problem adds soft time window to each customer based on the problem in Chapter 3, we improve the greedy heuristic algorithm provided by Chapter 3 to solve it, and give an example to illustrate the algorithm. Key words: 1-PDTSP, fuel consumption, time windows, greedy heuristic algorithm, genetic algorithm 目 录 HYPERLINK \l _bookmark0 第一章 引 言 ............................