带时间窗装卸一体化车辆路径问题的混合离散粒子群优化算法

摘要/Abstract

摘要：

为了同时实现总配送成本最低、车辆数最少和车辆行驶距离最短等目标，考虑车辆指派成本及运输路径成本的相对重要性，建立了带时间窗装卸一体化车辆路径问题的混合整数规划模型。针对该问题搜索空间的离散性和求解算法的局部收敛性，提出了一种混合离散粒子群求解算法。算法基于客户排列的直观无分段大路径解表示法，采用改进深度优先搜索分割法对问题解进行解码与评价；嵌入一种变邻域下降搜索程序并在个体粒子每次迭代时以一定概率选择执行，利用混合粒子群算法在多邻域深度搜索和在全局空间广度搜索进行寻优，同时应用模拟退火思想和比例选择性变异最差个体来改善个体搜索停滞现象。采用两个不同目标算例进行寻优测试，验证了所提算法的可行性和有效性。

关键词: 带时间窗车辆路径问题, 装卸一体化, 离散粒子群优化算法, 变邻域下降搜索

Abstract:

Considering the relative importance of dispatching cost of vehicles and travelling cost of routes, a mixed integer mathematical formulation of the vehicle routing problem with time windows and simultaneous pickup and delivery (VRPTWSPD) was established to make the total delivery cost, the number of vehicles and the travel cost minimize simultaneously. A hybrid discrete particle swarm optimization algorithm was proposed for solving VRPTWSPD. Solutions of algorithm were represented by an intuitive fragment-free giant tour of a permutation of all customers, and were decoded and evaluated by the revised depth first search split procedure. A variable neighborhood descent search procedure was carried out under a certain probability for individuals at each iteration, so that individuals could update with depth search in multi-neighborhood and with bread search in global exploration. The simulated annealing idea and mutating a selective portion of worst individuals were applied to improve the stagnation of the search. The feasibility and effectiveness of the proposed algorithm were verified by two instances with different goals.

Key words: vehicle routing problem with time window, simultaneous pickup and delivery, discrete particle swarm optimization, variable neighborhood descent search

中图分类号:

周蓉, 沈维蕾, 刘明周, 赵韩. 带时间窗装卸一体化车辆路径问题的混合离散粒子群优化算法[J]. 中国机械工程, 2016, 27(04): 494-502.

Hefei University of Technology, Hefei, . A Hybrid Discrete Particle Swarm Optimization Algorithm for Vehicle Routing Problemwith Time Windows and Simultaneous Pickup and Delivery[J]. China Mechanical Engineering, 2016, 27(04): 494-502.

参考文献

[1]Berbeglia G, Cordeau J F, Gribkovskaia I, et al. Static Pickup and Delivery Problems: a Classification Scheme and Survey[J].TOP,2007,15(1):1-31.

[2]郎茂祥. 物流配送车辆调度问题的模型和算法研究[D]. 北京：北方交通大学, 2002.

[3]Min H. The Multiple Vehicle Routing Problem with Simultaneous Delivery and Pick-up Points [J]. Transportation Research Part A General, 1989, 23(5): 377-386.

[4]Dethloff J. Vehicle Routing and Reverse Logistics: the Vehicle Routing Problem with Simultaneous Delivery and Pick-up [J]. Or Spectrum, 2001, 23(1): 79-96.

[5]Bianchessi N, Righini G.Heuristic Algorithms for the Vehicle Routing Problem with Simultaneous Pick-up and Delivery [J]. Computers & Operations Research,2007,34:578-594.

[6]李雪, 聂兰顺, 齐文艳,等. 基于近似动态规划的动态车辆调度算法[J].中国机械工程,2015,26(5):682-688.

Li Xue,Nie Lanshun,Qi Wenyan,et al.An Algorithm of Dynamic Vehicle Scheduling Problem Based on Approximate Dynamic Programming[J].China Mechanical Engineering, 2015, 26(5):682-688.

[7]Ai T J, Kachitvichyanukul V. A Particle Swarm Optimization for the Vehicle Routing Problem with Simultaneous Pickup and Delivery [J].Computers & Operations Research,2009,36:1693-1702.

[8]Gajpal Y, Abad P. An Ant Colony System (ACS) for Vehicle Routing Problem with Simultaneous Delivery and Pickup [J]. Computers & Operations Research, 2009,36:3215- 3223.

[9]Angelelli E, Mansini R. A Branch-and-price Algorithm for a Simultaneous Pick-up and Delivery Problem [C]// Lecture Notes in Economics and Mathematical Systems.USA: Springer, 2002: 249-267.

[10]Lai Mingyong, Cao Erbao. An Improved Differential Evolution Algorithm for Vehicle Routing Problem with Simultaneous Pickups and Deliveries and Time Windows [J]. Engineering Applications of Artificial Intelligence, 2010, 23:188-195.

[11]Wang H F, ChenY Y. A Genetic Algorithm for the Simultaneous Delivery and Pickup Problems with Time Window [J]. Computers & Industrial Engineering, 2012, 62: 84-95.

[12]王超, 穆东. 基于模拟退火算法求解VRPSPDTW问题[J]. 系统仿真学报, 2014,11(6):2618-2623. Wang Chao, Mu Dong. Solving VRPSPDTW Problem Using Simulated Annealing Algorithm[J]. Journal of System Simulation, 2014, 11(6):2618-2623.

[13]Boubahri L, Addouche S A, Mhamedi A E. Multi- ant Colonies Algorithms for the VRPSPDTW [C]// 2011 International Conference on Communications, Computing and Control Applications (CCCA).NewYork:IEEE,2011: 1-6.

[14]邱晗光, 张旭梅. 基于改进粒子群算法的开放式定位-运输路线问题研究[J]. 中国机械工程, 2006, 17(22): 2359-2361.

Qiu Hanguang, Zhang Xumei. Research on Open Location Routing Problem Based on Improved Particle Swarm Optimization Algorithm [J]. China Mechanical Engineering, 2006, 17(22): 2359-2361.

[15]Pan Q K, Tasgetiren M F, Liang Y C. A Discrete Particle Swarm Optimization Algorithm for the No-wait Flowshop Scheduling Problem [J]. Computers & Operations Research, 2008, 35: 2807-2839.

[16]郭文忠, 陈国龙, 陈振. 离散粒子群优化算法综述[J]. 福州大学学报(自然科学版), 2011, 39(5): 631-638.

Guo Wenzhong，Chen Guolong，Chen Zhen. Survey on Discrete Particle Swarm Optimization algorithm [J]. Journal of Fuzhou University( Natural Science Edition), 2011, 39(5): 631-638.

[17]Prins C. A Simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem [J]. Computers & Operations Research, 2004, 31: 1985-2002.

[18]Beasley J E. Route-first Cluster-second Methods for Vehicle Routing [J]. Omega, 1983, 11:403-408.

[19]Duhamel C, Lacomme P, Prodhon C. A Hybrid Evolutionary Local Search with Depth First Search Split Procedure for the Heterogeneous Vehicle Routing Problems [J]. Engineering Applications of Artificial Intelligence, 2012, 25: 345-358.

[20]Duhamel C, Lacomme P, Prodhon C. Efficient Frameworks for Greedy Split and New Depth First Search Split Procedures for Routing Problems [J]. Computers & Operations Research, 2011, 38: 723-739.

[21]庄英群. 应用禁忌搜索法于混合送收货之车辆途程问题[D] .台中:逢甲大学, 2003.