An improved ant colony algorithm for multi-objective vehicle routing problem with simultaneous pickup and delivery

被引：4

作者：

Chen X.-Q. ^{[1
]}

Hu D.-W. ^{[1
]}

Yang Q.-Q. ^{[1
]}

Hu H. ^{[1
]}

Gao Y. ^{[1
]}

机构：

[1] School of Automobile, Chang'an University, Xi'an

来源：

Kongzhi Lilun Yu Yingyong/Control Theory and Applications | 2018年 / 35卷 / 09期

基金：

中国国家自然科学基金;

关键词：

Ant colony algorithm; Greedy search; Integrated transportation planning; Logistics engineering; Multi-objective iterated local search; Vehicle routing problem; with simultaneous pickup and delivery;

D O I：

10.7641/CTA.2018.80085

中图分类号：

学科分类号：

摘要：

In order to minimize the total cost and maximum gap among each tour in vehicle routing problems with simultaneous pickup and delivery (VRPSPD), a VRPSPD bi-objective model which considers the vehicle capacity and distance constrain simultaneously was established. The accuracy of the model was verified by testing in a commercial software. Then a specific multi objective ant colony optimization algorithm with an embedded tabu list and a greedy transfer rule was designed based on the definition of the problem. To optimize the solutions or generate new Pareto solutions in various neighborhoods, a multi-objective iterated local search procedure was executed on solutions obtained by ants. Response surface methodology was used to fit the mathematical relation of parameters and the objective functions in order to determine the best parameter combination. 12 sets of Solomon benchmark instances from literature were solved and Pareto solutions were obtained by the algorithm. The solutions with lowest cost (absolute preference to minimize the costs) from Pareto solutions were compared with previous results by several algorithms from literature which minimize the total costs only. The results indicate that the Pareto solutions acquired by the proposed algorithm provide good tradeoff between two objectives and yield approximate optimal of each single objective. © 2018, Editorial Department of Control Theory & Applications South China University of Technology. All right reserved.

引用

页码：1347 / 1356

页数：9

共 20 条

[1]

Goetschalckx M., Jacobs-Blecha C., The vehicle routing problem with backhauls, European Journal of Operational Research, 42, 1, pp. 39-51, (1987)

[2]

Min H., The multiple vehicle routing problem with simultaneous delivery and pick-up points, Transportation Research Part A General, 23, 5, pp. 377-386, (1989)

[3]

Wang C., Mu D., Solving VRPSPDTW problem using simulated annealing algorithm, Journal of System Simulation, 26, 11, pp. 2618-2623, (2014)

[4]

Wang C., Mu D., Zhao F., Et al., A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup-delivery and time windows, Computers & Industrial Engineering, 83 C, pp. 111-122, (2015)

[5]

Duan F., The simultaneous pick-up and delivery VRP with carbon emissions fee, Journal of Natural Science of Hunan Normal University, 38, 3, pp. 69-73, (2015)

[6]

Zhao Y., Li W., Zhang J., Et al., Low carbon for a multi-vehicle routing problem with simultaneous pickups and deliveries, Journal of Zhejiang University of Technology, 43, 1, pp. 18-23, (2015)

[7]

Tan W., Wen Q., To solve the pickup delivery vehicle routing problem based on ant system and 2-opt method, Mathematics in Practice and Theory, 45, 24, pp. 235-242, (2015)

[8]

Li J., Pardalos P.M., Sun H., Et al., Iterated local search embedded adaptive neighborhood selection approach for the multi-depot vehicle routing problem with simultaneous deliveries and pickups, Expert Systems with Applications An International Journal, 42, 7, pp. 3551-3561, (2015)

[9]

Avci M., Topaloglu S., An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries, Computers & Industrial Engineering, 83, pp. 15-29, (2015)

[10]

Avci M., Topaloglu S., A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery, Expert Systems with Applications, 53 C, pp. 160-171, (2016)

← 1 2 →