Study On One-commodity Pickup And Delivery Traveling Salesman Problems With Fuel Consumption

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.