Abstract：This paper studied a bi-objective vehicle routing problem with time windows, variable speed, multiple path choice, and capacity constraints (BOVRPTWVDPC) in a complex road network aiming at minimizing the total cost of distribution and maximizing the overall customer satisfaction. In modelling of customer’s satisfaction, the factors of distribution time window and customer priority were taken into account, and in the description of vehicle speed, the traffic period and road conditions were considered. A bi-objective mixed integer programming model was established, and an improved ant colony algorithm was designed to solve the problem. The simulation results show that the proposed model and the improved algorithm are effective and have certain reference value for vehicle distribution path planning under complex road conditions.
[1] DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91. [2] MALANDRAKI C, DASKIN M S. Time dependent vehicle routing problems: formulations, properties and heuristic algorithms[J]. Transportation Science, 1992, 26(3): 185-200. [3] 周鲜成,刘长石,周开军,等.时间依赖型绿色车辆路径模型及改进蚁群算法[J].管理科学学报, 2019, 22(5): 57-68. ZHOU X C, LIU C S, ZHOU K J, et al. Improved ant colony algorithm and modeling of time-dependent green vehicle routing problem[J]. Journal of Management Sciences in China, 2019, 22(5): 57-68. [4] POONTHALIR G, NADARAJAN R. A fuel efficient green vehicle routing problem with varying speed constraint (F-GVRP)[J]. Expert Systems With Applications, 2018, 100: 131-144. [5] FAN H M, ZHANG Y G, TIAN P J, et al. Time-dependent multi-depot green vehicle routing problem with time windows considering temporal-spatial distance[J].Computers and Operations Research,2021,129:105211. [6] GMIRA M, GENDREAU M, LODI A, et al. Tabu search for the time-dependent vehicle routing problem with time windows on road network[J]. European Journal of Operational Research, 2021, 288(1): 129-140. [7] BEHNKE M, KIRSCHSTEIN T. The impact of path selection on GHG emissions in city logistics[J]. Transportation Research Part E, 2017, 106: 320-336. [8] WANG L, GAO S, WANG K, et al. Time-dependent electric vehicle routing problem with time windows and path flexibility[J]. Journal of Advanced Transportation, 2020, 3030197: 1-19. [9] 李顺勇,但斌,葛显龙.多通路时变网络下低碳车辆路径优化模型与算法[J].计算机集成制造系统, 2019, 25(2): 454-468. LI S Y, DAN B, GE X L. Optimization model and algorithm of low carbon vehicle routing problem under multi-graph time-varying network[J]. Computer Integrated Manufacturing Systems, 2019, 25(2): 454-468. [10] 程兴群,金淳,姚庆国,等.碳交易政策下多式联运路径选择问题的鲁棒优化研究[J].中国管理科学, 2021, 29(6): 82-90. CHENG X Q, JIN C, YAO Q G, et al. Research on robust optimization for route selection problem in multimodal transportation under the cap and trade policy[J]. Chinese Journal of Management Science, 2021, 29(6): 82-90. [11] SUN J Y, HUANG J L, CHEN Y Y, et al. Flexible bus route optimization for multitarget stations[J]. Mathematical Problems in Engineering, 2020: 1-8. [12] IGNAZIO A C, GIUSEPPE M, CORRADO R, et al. Route and path choices of freight vehicles: a case study with floating car data[J]. Sustainability, 2020, 12(20): 8557-8557. [13] 余建军,程文琪,吴永忠.考虑顾客满意度的生鲜外卖路径规划[J].工业工程与管理, 2021, 26(4): 158-167. YU J J, CHENG W Q, WU Y Z. Path planning of fresh takeout considering customer satisfaction[J]. Industrial Engineering and Management, 2021, 26(4): 158-167. [14] BARKAOUI M, BERGER J, BOUKHTOUTA A. Customer satisfaction in dynamic vehicle routing problem with time windows[J]. Applied Soft Computing, 2015, 35: 423-432. [15] RAJAK S, PARTHIBAN P, DHANALAKSHMI R. Multi-depot vehicle routing problem based on customer satisfaction[J]. International Journal of Services Technology and Management, 2020, 26(2/3): 252-265. [16] SONG M X, LI J Q, HAN Y Q, et al. Metaheuristics for solving the vehicle routing problem with the time windows and energy consumption in cold chain logistics[J]. Applied Soft Computing, 2020, 95: 10651. [17] Afshar-Bakeshloo M, Mehrabi A, Safari H, et al. A green vehicle routing problem with customer satisfaction criteria[J]. Journal of Industrial Engineering International, 2016, 12(4): 529-544. [18] Guerriero F, Surace R, Loscrí V, et al. A multi-objective approach for unmanned aerial vehicle routing problem with soft time windows constraints[J]. Applied Mathematical Modelling, 2014, 38(3): 839-852. [19] 汪定伟, 王俊伟, 王洪峰. 智能优化算法[M]. 北京: 高等教育出版社, 2007: 166-167.
