Intelligent Water Drops Algorithm for Vehicle Routing Problem with Multiple Time Windows

doi:10.12005/orms.2015.189

Abstract

Abstract: The vehicle routing problem with multiple time windows is investigated in this paper. The constraints of vehicle’s capacity and the multiple hard time windows are considered. An integer linear programming model of VRPMTW is proposed, and the objective function is to minimize the total costs including the fixed costs of vehicles and the transportation costs of vehicles. Based on the principles of the intelligent water drops, an Intelligent Water Drops(IDW)algorithm for solving the VRPMTW is designed. We further do simulation on an example, and compare the results obtained by IDW algorithm and GA(genetic algorithm)algorithm. The results show that we can find the global optimal solution of VRPMTW with higher probability using Intelligent Water Drops algorithm than Genetic Algorithm. IDW algorithm is an efficient algorithm for solving VRPMTW.

Key words: vehicle routing problem, multiple time windows, mathematical model, intelligent water drops algorithm

摘要： 研究了多时间窗车辆路径问题,考虑了车容量、多个硬时间窗限制等约束条件,以动用车辆的固定成本和车辆运行成本之和最小为目标,建立了整数线性规划模型。根据智能水滴算法的基本原理,设计了求解多时间窗车辆路径问题的快速算法,利用具体实例进行了模拟计算,并与遗传算法的计算结果进行了对比分析,结果显示,利用智能水滴算法求解多时间窗车辆路径问题,能够以很高的概率得到全局最优解,是求解多时间窗车辆路径问题的有效算法。

关键词: 车辆路径问题, 多时间窗, 数学模型, 智能水滴算法

CLC Number:

O226

LI Zhen-ping, ZHAO Fei, LIU Hong-wei. Intelligent Water Drops Algorithm for Vehicle Routing Problem with Multiple Time Windows[J]. Operations Research and Management Science, 2015, 24(6): 1-10.

李珍萍, 赵菲, 刘洪伟. 多时间窗车辆路径问题的智能水滴算法[J]. 运筹与管理, 2015, 24(6): 1-10.

References

[1] Dantzig G, Ramser J. The truck dispatching problem[J]. Management Science, 1959, 10 (6): 80-91.
[2] Shi Z, Fu Z. Research on two-phase chain store distribution vehicle routing problem with soft time windows[J]. Application Research of Computers, 2012, 29 (9): 94-99.
[3] Ma H, Zuo C, Yand S. Modeling and solving for vehicle routing problem with multiple time windows[J]. Journal of System Engineering, 2009,24, (05): 607-613.
[4] Peng B, Zhou Y. Hybrid ant colony algorithm for vehicle routing problem with multiple time windows[J]. Computer Engineering and Applications, 2010, 46 (31): 28-31.
[5] Huang Q, Li Z. Mathematical model and algorithm for vehicle routing problem with multiple time windows[J]. Logistics Technology, 2012, 31(7): 194-196.
[6] Hamed Shah-Hosseini. (2007). Problem Solving by Intelligent Water Drops[A]. Proceedings of the IEEE Congress on Evolutionary Computation, Singapore, 2007. 3226-3231.
[7] Hamed Shah-Hosseini. The intelligent water drops algorithm: a nature-inspired swarm-based optimization algorithm[J]. Bio-Inspired Computation, 2009, Vol. 1, Nos. 1/2. 71-79.
[8] Hamed Shah-Hosseini. Optimization with the nature-inspired intelligent water drops[A]. In W. P. Dos Santos(Eds), Evolutionary computation, Austria: I-Tech, Vienna, 2009. 297-320.
[9] Hamed Shah-Hosseini. Intelligent water drops algorithm for automatic multilevel thresholding of gray-level images using a modified Otsu’s criterion[J]. International Journal of Modeling, Identification and Control(IJMIC), 2012, 15(4): 241-249.
[10] Kamkar, Akbarzaden, Yaghoobi. Intelligent water drops a new optimization algorithm for solving the Vehicle Routing Problem[A]. IEEE International Conference on Systems Man and Cybernetics, 2010. 4142-4146
[11] Tavakkoli-Moghaddam R, Safaei N, Ghlipour Y. A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length[J]. Applied Mathematics and Computation, 2006, 176: 445-454
[12] Prins C. A simple and effective evolutionary algorithm for the vehicle routing problem[J]. Computers & Operations Research, 2004, 31: 1985-2002.
[13] Geonwook Jeon, Herman R. Leep, Jae Young Shim. A vehicle routing problem solved by a hybrid genentic algorithm[J]. Journal of Computers and Industrial Engineering, 2007, 53(4): 680-692.
[14] Renaud J, Laporte G, Boctor F F. A tabu search heuristic for the multi-depot vehicle routing problem[J]. Computers & Operations Research, 1996, 23 (3): 229-235.
[15] Doerner K F, Hartl R F, Kiechle G, Lucka M, Reimann M. Parallel ant systems for the capacitated vehicle routing problem[A]. Evolutionary Computation in Combinatorial Optimization: 4th European Conference, EvoCOP 2004, LNCS 3004, 72-83.
[16] Reimann M, Stummer M, Doemer K. (2002).A savings based ant system for the vehicle routing problem. Langdon,W.B. et al.(Eds), GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference, Morgan Kaufmann, San Francisco.
[17] Peng W, Tong R F, Tang M, Dong J X. (2005). Ant colony search algorithms for optimal packing problem. ICNC 2005, LNCS 3611, 1229-1238.
[18] Msallam M M, Hamdan M. Improved intelligent water drops algorithm using adaptive schema[J]. Bio-Inspired Computation, 2011,3(2): 103-111.
[19] Hamed Shah-Hosseini. (2012). An approach to continuous optimization by the intelligent water drops algorithm. The 4th International Conference of Cognitive Science, 224-229.
[20] Niu S H, Ong S K, Nee A Y C. An improved intelligent water drops algorithm for achieving optimal job-shop scheduling solutions[J]. International Journal of Production Research, 2012, 50: 15, 4192-4205
[21] Hamed Shah-Hosseini. Intelligent water drops algorithm: a new optimization method for solving the multiple knapsack problem[J]. International Journal of Intelligent Computing and Cybernetics, 2008, 1(2): 193-212.
[22] Duan H, Liu S, Lei X. (2008). Air robot path planning based on intelligent water drops optimization. IEEE International Joint Conference on Neural Networks(IJCNN2008), 1(8): 1397-1401.
[23] Duan H, Liu S, Wu J. Novel intelligent water drops optimization approach to single UCAV smooth path planning[J]. Aerospace Science and Technology, 2009, 13: 442-449.