Similar articles

Abstract: We investigate a kind of vehicle routing problem with constraints (VRPC) in the car-sharing mobility environment, where the problem is based on user orders, and each order has a reservation time limit and two location point transitions, origin and destination. It is a typical extended vehicle routing problem (VRP) with both time and space constraints. We consider the VRPC problem characteristics and establish a vehicle scheduling model to minimize operating costs and maximize user (or passenger) experience. To solve the scheduling model more accurately, a spatiotemporal distance representation function is defined based on the temporal and spatial properties of the customer, and a spatiotemporal distance embedded hybrid ant colony algorithm (HACA-ST) is proposed. The algorithm can be divided into two stages. First, through spatiotemporal clustering, the spatiotemporal distance between users is the main measure used to classify customers in categories, which helps provide heuristic information for problem solving. Second, an improved ant colony algorithm (ACO) is proposed to optimize the solution by combining a labor division strategy and the spatiotemporal distance function to obtain the final scheduling route. Computational analysis is carried out based on existing data sets and simulated urban instances. Compared with other heuristic algorithms, HACA-ST reduces the length of the shortest route by 2%–14% in benchmark instances. In VRPC testing instances, concerning the combined cost, HACA-ST has competitive cost compared to existing VRP-related algorithms. Finally, we provide two actual urban scenarios to further verify the effectiveness of the proposed algorithm.

采用嵌入时空距离的混合蚁群算法求解一类受限车辆路径问题

[1]Alemi F, Circella G, Mokhtarian P, et al., 2019. What drives the use of ridehailing in California? Ordered probit models of the usage frequency of Uber and Lyft. Transp Res Part C Emerg Technol, 102:233-248.

[2]Baños R, Ortega J, Gil C, et al., 2013. A hybrid meta-heuristic for multi-objective vehicle routing problems with time windows. Comput Ind Eng, 65(2):286-296.

[3]Beheshti AK, Hejazi SR, 2015. A novel hybrid column generation-metaheuristic approach for the vehicle routing problem with general soft time window. Inform Sci, 316:598-615.

[4]Bonabeau E, Dorigo M, Theraulaz G, 2000. Inspiration for optimization from social insect behaviour. Nature, 406(6791):39-42.

[5]Brandão J, 2020. A memory-based iterated local search algorithm for the multi-depot open vehicle routing problem. Eur J Oper Res, 284(2):559-571.

[6]Chapman DA, Eyckmans J, van Acker K, 2020. Does car-sharing reduce car-use? An impact evaluation of car-sharing in Flanders, Belgium. Sustainability, 12(19):8155.

[7]Chen DL, Yao MD, Liu H, 2020. Research on Optimization Method and Platform of Car-Sharing Scheduling. Publishing House of Electronics Industry, Beijing, China, p.76-86(in Chinese).

[8]Chen YY, Wu HS, Xiao RB, 2022. Improved wolf pack algorithm for UAV path planning problem. Int J Swarm Intell Res, 13(1):1-22.

[9]Dang YB, Allen TT, Singh M, 2022. A heterogeneous vehicle routing problem with common carriers and time regulations: mathematical formulation and a two-color ant colony search. Comput Ind Eng, 168:108036.

[10]Dantzig GB, Ramser JH, 1959. The truck dispatching problem. Manag Sci, 6(1):80-91.

[11]Dorigo M, Gambardella LM, 1997. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans Evol Comput, 1(1):53-66.

[12]Elsedimy E, Algarni F, 2022. MOTS-ACO: an improved ant colony optimiser for multi-objective task scheduling optimisation problem in cloud data centres. IET Netw, 11(2):43-57.

[13]Errico F, Desaulniers G, Gendreau M, et al., 2018. The vehicle routing problem with hard time windows and stochastic service times. Euro J Transp Log, 7(3):223-251.

[14]Feng ZH, Xiao RB, 2022. Extended ant colony algorithm based on mixed feedback mechanism. Contr Dec, 37(12):3160-3170(in Chinese).

[15]Hu SH, Chen P, Lin HF, et al., 2018. Promoting carsharing attractiveness and efficiency: an exploratory analysis. Transp Res Part D Transp Environ, 65:229-243.

[16]Jia YH, Mei Y, Zhang MJ, 2022. A bilevel ant colony optimization algorithm for capacitated electric vehicle routing problem. IEEE Trans Cybern, 52(10):10855-10868.

[17]Jiang HW, Guo T, Yang Z, 2022. Research progress of vehicle routing problem. Acta Electron Sin, 50(2):480-492(in Chinese).

[18]Jiang HZ, Zhang XY, 2019. An experimental model of regulating the sharing economy in China: the case of online car hailing. Comput Law Secur Rev, 35(2):145-156.

[19]Li G, Wang GG, Xiao RB, 2022. A novel adaptive weight algorithm based on decomposition and two-part update strategy for many-objective optimization. Inform Sci, 615:323-347.

[20]Lin S, Kernighan BW, 1973. An effective heuristic algorithm for the traveling-salesman problem. Oper Res, 21(2):498-516.

[21]Ma J, Chen LX, Mahmood A, 2019. One-way car-sharing system based on recharging strategy. Chinese Control Conf, p.2290-2294.

[22]Meng XP, Pian ZY, Shen ZY, 2013. Ant algorithm based on direction-coordinating. Contr Dec, 28(5):782-786(in Chinese).

[23]Nourinejad M, Roorda MJ, 2014. A dynamic carsharing decision support system. Transp Res Part E Log Trans Rev, 66:36-50.

[24]Qi MY, Lin WH, Li N, et al., 2012. A spatiotemporal partitioning approach for large-scale vehicle routing problems with time windows. Trans Res Part E Log Trans Rev, 48(1):248-257.

[25]Sitek P, Wikarek J, Rutczyńska-Wdowiak K, et al., 2021. Optimization of capacitated vehicle routing problem with alternative delivery, pick-up and time windows: a modified hybrid approach. Neurocomputing, 423:670-678.

[26]Solomon MM, 1987. Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper Res, 35(2):254-265.

[27]Sowmya R, Sankaranarayanan V, 2022. Optimal vehicle-to-grid and grid-to-vehicle scheduling strategy with uncertainty management using improved marine predator algorithm. Comput Electr Eng, 100:107949.

[28]Wang WJ, 2010. Improved genetic algorithm for vehicle routing problem with time windows. Int Conf on Intelligent Computing and Cognitive Informatics, p.203-206.

[29]Wang Y, Zhang J, Assogba K, et al., 2018a. Collaboration and transportation resource sharing in multiple centers vehicle routing optimization with delivery and pickup. Knowl-Based Syst, 160:296-310.

[30]Wang Y, Assogba K, Liu Y, et al., 2018b. Two-echelon location-routing optimization with time windows based on customer clustering. Expert Syst Appl, 104:244-260.

[31]Wang Y, Wang L, Chen GC, et al., 2020. An improved ant colony optimization algorithm to the periodic vehicle routing problem with time window and service choice. Swarm Evol Comput, 55:100675.

[32]Wang Y, Ran LY, Guan XY, et al., 2022. Collaborative multicenter vehicle routing problem with time windows and mixed deliveries and pickups. Expert Syst Appl, 197:116690.

[33]Xiao RB, Chen ZZ, 2023. From swarm intelligence optimization to swarm intelligence evolution. J Nanchang Inst Technol, 42(1):1-10(in Chinese).

[34]Xiao RB, Wang YC, 2018. Labour division in swarm intelligence for allocation problems: a survey. Int J Bio-Inspir Comput, 12(2):71-86.

[35]Xiao RB, Feng ZH, Wang JH, 2022. Collective intelligence: conception, research progresses and application analyses. J Nanchang Inst Technol, 41(1):1-21(in Chinese).

[36]Yang XT, Zhang T, Bai LP, et al., 2019. Appointment scheduling and routing problem of community-home-health-care: based on modified ant-colony algorithm. Syst Eng Theory Pract, 39(5):1212-1224(in Chinese).

[37]Yu VF, Jodiawan P, Redi AANP, 2022. Crowd-shipping problem with time windows, transshipment nodes, and delivery options. Transp Res Part E Log Transp Rev, 157:102545.

[38]Zhang JL, Zhao YW, Wang HW, et al., 2017. Multi-objective cooperative QEA for low-carbon time dependent vehicle routing problem with simultaneous delivery and pickup. Int J Wirel Mob Comput, 12(4):400.

[39]Zhang WQ, Yang DJ, Zhang GH, et al., 2020. Hybrid multiobjective evolutionary algorithm with fast sampling strategy-based global search and route sequence difference-based local search for VRPTW. Expert Syst Appl, 145:113151.

[40]Zhang WY, Xia DW, Chang GY, et al., 2022. APFD: an effective approach to taxi route recommendation with mobile trajectory big data. Front Inform Technol Electron Eng, 23(10):1494-1510.