Improved Ant Colony Optimization for Seafood Product Delivery Routing Problem

  • Baozhen Yao School of Automotive Engineering, Dalian University of Technology Dalian, 116024, China
  • Ping Hu School of Automotive Engineering, Dalian University of Technology Dalian, 116024, China
  • Mingheng Zhang School of Automotive Engineering, Dalian University of Technology Dalian, 116024, China
  • Xiaomei Tian CTS International Logistics Corporation Limited Dalian, 116001, China
Keywords: Seafood Product Delivery Routing Problem, Multi-Depot Open Vehicle Routing Problem, Ant Colony Optimization, Adaptive Strategy, Crossover Operation

Abstract

This paper deals with a real-life vehicle delivery routing problem, which is a seafood product delivery routing problem. Considering the features of the seafood product delivery routing problem, this paper formulated this problem as a multi-depot open vehicle routing problem. Since the multi-depot open vehicle routing problem is a very complex problem, a method is used to reduce the complexity of the problem by changing the multi-depot open vehicle routing problem into an open vehicle routing problem with a dummy central depot in this paper. Then, ant colony optimization is used to solve the problem. To improve the performance of the algorithm, crossover operation and some adaptive strategies are used. Finally, the computational results for the benchmark problems of the multi-depot vehicle routing problem indicate that the proposed ant colony optimization is an effective method to solve the multi-depot vehicle routing problem. Furthermore, the computation results of the seafood product delivery problem from Dalian, China also suggest that the proposed ant colony optimization is feasible to solve the seafood product delivery routing problem.

References

Jaffry, S., Pickering, H., Ghulam, Y., Whitmarsh, D., Wattage, P.: (2004); Consumer choices for quality and sustainability labelled seafood products in the UK. Food Policy 29(3):215–228

Guillotreau, P., Peridy, N.: (2000); Trade barriers and European imports of seafood products: a quantitative assessment. Marine Policy, 24(5):431-437

Salari, M., Toth, P., Tramontani, A.: (2010); An ILP improvement procedure for the Open Vehicle Routing Problem. Computers & Operations Research, 37(12):2106-2120.

Brandao, J.: (2004); A tabu search algorithm for the open vehicle routing problem. European Journal of Operational Research, 157(3):552-564

Renaud, J., Laporte, G., Boctor, F.F.: (1996); A Tabu Search Heuristic for the Multi-Depot Vehicle Routing Problem. Computers & Operations Research, 23(3):229-235

Yu, B., Yang, Z.Z., Xie, J.X.: (2011); A parallel improved ant colony optimization for multi-depot vehicle routing problem. Journal of the Operational Research Society, 62:183-188

Chen, G., Govindan, K., and Yang, Z.Z.: (2013); Managing truck arrivals with time windows to alleviate gate congestion at container terminals, International Journal of Production Economics, 141(1):179-188

Chen, G., Yang, Z.Z.: (2010); Optimizing Time Windows for Managing Arrivals of Export Container in Chinese Container Terminals, Maritime Economics & Logistics, 12(1):111-126

Yao, B.Z., Hu, P., Lu, X.H., Gao, J.J. Zhang, M.H.: (2013); Transit network design based on travel time reliability. Transportation Research Part C, DOI:10.1016/j.trc.2013.12.005(in press).

Yao B.Z., Hu, P., Zhang, M.H., Wang, S.: (2013); Artificial Bee Colony Algorithm with Scanning Strategy for Periodic Vehicle Routing Problem. SIMULATION: Transactions of the Society for Modeling and Simulation International. 89(6):762-770

Yao, B.Z., Yang, C.Y., Yao, J.B., Sun, J.: (2010); Tunnel Surrounding Rock Displacement Prediction Using Support Vector Machine. International Journal of Computational Intelligence Systems, 3(6): 843-852

Yu, B., Yang, Z.Z.: (2011); An ant colony optimization model: The period vehicle routing problem with time windows. Transportation Research Part E, 47(2):166-181

Yu, B., Lam, W.H.K., Lam, T.M.: (2011); Bus Arrival Time Prediction at Bus Stop with Multiple Routes. Transportation Research Part C, 19(6):1157-1170

Yu, B., Yang, Z.Z., LI, S.: (2012); Real-Time Partway Deadheading Strategy Based on Transit Service Reliability Assessment. Transportation Research Part A, 46(8):1265-1279

Yue, M., Zhang, Y.S., Tang, F.Y.: (2013); Path following control of a two-wheeled surveillance vehicle based on sliding mode technology. Transaction of the Institute of Measurement and Control, 35(2): 212-218

Repoussisa, P.P., Tarantilisa, C.D., Bräysyb, O., Ioannoua, G.: (2010); A hybrid evolution strategy for the open vehicle routing problem. Computers & Operations Research, 37(3):443-455

Mirabi, M., Fatemi Ghomib, S.M.T., Jolaic, F.: (2010); Efficient stochastic hybrid heuristics for the multi-depot vehicle routing problem. Robotics and Computer-Integrated Manufacturing, 26(6):564-569

Ho, W., Ho, G.T.S., Ji, P., Lau, H.C.W.: (2008); A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engineering Applications of Artificial Intelligence, 21(4):548-557

Dorigo, M., Maniezzo, V., Colorni, A.: (1996); The Ant System: Optimization by a Colony of Cooperating Agents, IEEE Transactions on Systems, Mans, and Cybernetics 1 (26), 29-41

Gambardella, L., Taillard, E., Dorigo, M.: (1997); Ant Colonies for the QAP, Technical Report 97-4, IDSIA, Lugano, Switzerland

Colorni, A., Dorigo, M., Maniezzo, V., Trubian, M.: (1994): Ant System for Job-Shop Scheduling, Jorbel -Belgian Journal of Operations Research Statistics and Computer Science 34 (1), 39–53

Schoonderwoerd, R., Holland, O., Bruten, J., Rothkrantz, L.: (1997); Ant-Based Load Balancing in Telecommunications Networks, Adaptive Behavior 5 (2), 169-207

Yu, B., Yang, Z.Z., Yao, B.Z.: (2009); An Improved Ant Colony Optimization for Vehicle Routing Problem. European Journal of Operational Research, 196(1):171-176

Clarke, G., Wright, J.W.: (1964); Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations research, 12(4):568-581

Croes, G.A.: 1958, A method for solving traveling salesman problems. Operations Research, 6: 791–812.

Bullnheimer, B., Hartl, R.F., Strauss, C.: (1997); Applying the Ant System to the Vehicle Routing Problem, in: Second Metaheuristics International Conference, MIC’97, Sophia-Antipolis, France.

Bullnheimer, B., Hartl, R.F., Strauss, C.: (1999); An Improved Ant System Algorithm for the Vehicle Routing Problem. Annals of Operations Research, 89, 319–28

Bell, J.E., McMullen, P.R.: (2004); Ant Colony Optimization Techniques for the Vehicle Routing Problem. Advanced Engineering Informatics 1;8, 41-48

Chen, C.H., Ting, C.J.: (2006); An Improved Ant Colony System Algorithm For The Vehicle Routing Problem. Journal of the Chinese Institute of Industrial Engineers, 23(2):115-126

Stützle, T. and Hoos, H.H.: (2000); MAX–MIN ant system, Future Generation Computer Systems, 16(8): 889-914

Christofides, N. and Eilon, S.: (1969); An algorithm for the vehicle dispatching problem. Journal of the Operational Research Society, 20: 309–318

Gillett, B.E., Johnson, J.G.: (1976); Multi-terminal vehicle-dispatch algorithm. Omega, 4(6):711-718

Chao, M.I., Golden, B.L. and Wasil, E.A.: (1993). A new heuristic for the multi-depot vehicle routing problem that improves upon best known solutions. American Journal of Mathematical and Management Sciences, 13(3-4):371-406

Cordeau, J.F., Gendreau, M. and Laporte, G.: (1997). A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks, 30: 105–119

How to Cite
1.
Yao B, Hu P, Zhang M, Tian X. Improved Ant Colony Optimization for Seafood Product Delivery Routing Problem. Promet [Internet]. 1 [cited 2023Feb.5];26(1):1-10. Available from: https://traffic.fpz.hr/index.php/PROMTT/article/view/1478
Section
Articles