Spatiotemporal distance embedded hybrid ant colony algorithm for a kind of vehicle routing problem with constraints

Zhenhui FENG; Renbin XIAO

doi:10.1631/FITEE.2200585

Your Location：

Home >

Browse articles >

Spatiotemporal distance embedded hybrid ant colony algorithm for a kind of vehicle routing problem with constraints

Regular Papers | Updated：2023-07-24

- Spatiotemporal distance embedded hybrid ant colony algorithm for a kind of vehicle routing problem with constraints
- 采用嵌入时空距离的混合蚁群算法求解一类受限车辆路径问题
- Frontiers of Information Technology & Electronic Engineering Vol. 24, Issue 7, Pages: 1062-1079(2023)
- Affiliations：
  
  1.School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China
  2.Institute of Artificial Intelligence, Huazhong University of Science and Technology, Wuhan 430074, China
  3.Key Laboratory of Image Information Processing and Intelligent Control, Ministry of Education, Wuhan 430074, China
- Author bio：
  
  E-mail: feng_zh@hust.edu.cn
  ‡Corresponding author
- Funds：
- DOI：10.1631/FITEE.2200585
  CLC： TP399
- Received：21 November 2022，
  
  Revised：2023-04-06，
  
  Published：0 July 2023
- Accepted：
Scan QR Code
Zhenhui FENG, Renbin XIAO. Spatiotemporal distance embedded hybrid ant colony algorithm for a kind of vehicle routing problem with constraints[J]. Frontiers of Information Technology & Electronic Engineering, 2023, 24(7): 1062-1079.
DOI：

Zhenhui FENG, Renbin XIAO. Spatiotemporal distance embedded hybrid ant colony algorithm for a kind of vehicle routing problem with constraints[J]. Frontiers of Information Technology & Electronic Engineering, 2023, 24(7): 1062-1079. DOI： 10.1631/FITEE.2200585.

摘要

本文研究了共享出行背景下一类受限车辆路径问题，该问题以用户订单为核心，每个订单具有预约时间限制以及起始点、目的地两个位置点转换，是典型的具有时间、空间双重约束的扩展车辆路径问题。根据该问题特征，我们建立了以运营成本最低和用户体验度最高为目标的路径规划模型。为更精确地求解模型，根据用户的时间和空间属性定义了时空距离表示函数，进而提出一种嵌入时空距离的混合蚁群算法。该算法可分为两个阶段，首先通过时空聚类，以用户之间时空距离为主要衡量指标对用户进行分类，为问题求解提供启发式信息；其次结合劳动分工策略和时空距离函数，提出一种改进蚁群算法进行优化求解，以得到最终调度路线。基于现有数据集和实际城市环境的仿真案例进行数值实验。与其他启发式算法相比，该算法将基准实例中求得的最短路径长度降低2%–14%；与其他现存路径规划算法相比，该算法在测试实例上求得的综合成本更有竞争力。最后，利用两个实际的城市环境仿真案例进一步验证了所提算法的有效性。

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.

关键词

Keywords

references

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 . https://doi.org/10.1016/j.trc.2018.12.016 https://doi.org/10.1016/j.trc.2018.12.016

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 . https://doi.org/10.1016/j.cie.2013.01.007 https://doi.org/10.1016/j.cie.2013.01.007

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 . https://doi.org/10.1016/j.ins.2014.11.037 https://doi.org/10.1016/j.ins.2014.11.037

Bonabeau E , Dorigo M , Theraulaz G , 2000 . Inspiration for optimization from social insect behaviour . Nature , 406 ( 6791 ): 39 - 42 . https://doi.org/10.1038/35017500 https://doi.org/10.1038/35017500

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 . https://doi.org/10.1016/j.ejor.2020.01.008 https://doi.org/10.1016/j.ejor.2020.01.008

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 . https://doi.org/10.3390/su12198155 https://doi.org/10.3390/su12198155

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) .

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 . https://doi.org/10.4018/IJSIR.302605 https://doi.org/10.4018/IJSIR.302605

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 . https://doi.org/10.1016/j.cie.2022.108036 https://doi.org/10.1016/j.cie.2022.108036

Dantzig GB , Ramser JH , 1959 . The truck dispatching problem . Manag Sci , 6 ( 1 ): 80 - 91 . https://doi.org/10.1287/mnsc.6.1.80 https://doi.org/10.1287/mnsc.6.1.80

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 . https://doi.org/10.1109/4235.585892 https://doi.org/10.1109/4235.585892

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 . https://doi.org/10.1049/ntw2.12033 https://doi.org/10.1049/ntw2.12033

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 . https://doi.org/10.1007/s13676-016-0101-4 https://doi.org/10.1007/s13676-016-0101-4

Feng ZH , Xiao RB , 2022 . Extended ant colony algorithm based on mixed feedback mechanism . Contr Dec , 37 ( 12 ): 3160 - 3170 (in Chinese) . https://doi.org/10.13195/j.kzyjc.2021.0846 https://doi.org/10.13195/j.kzyjc.2021.0846

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 . https://doi.org/10.1016/j.trd.2018.08.015 https://doi.org/10.1016/j.trd.2018.08.015

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 . https://doi.org/10.1109/TCYB.2021.3069942 https://doi.org/10.1109/TCYB.2021.3069942

Jiang HW , Guo T , Yang Z , 2022 . Research progress of vehicle routing problem . Acta Electron Sin , 50 ( 2 ): 480 - 492 (in Chinese) . https://doi.org/10.12263/DZXB.20201154 https://doi.org/10.12263/DZXB.20201154

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 . https://doi.org/10.1016/j.clsr.2018.12.008 https://doi.org/10.1016/j.clsr.2018.12.008

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 . https://doi.org/10.1016/j.ins.2022.09.057 https://doi.org/10.1016/j.ins.2022.09.057

Lin S , Kernighan BW , 1973 . An effective heuristic algorithm for the traveling-salesman problem . Oper Res , 21 ( 2 ): 498 - 516 . https://doi.org/10.1287/opre.21.2.498 https://doi.org/10.1287/opre.21.2.498

Ma J , Chen LX , Mahmood A , 2019 . One-way car-sharing system based on recharging strategy . Chinese Control Conf , p. 2290 - 2294 . https://doi.org/10.23919/ChiCC.2019.8865185 https://doi.org/10.23919/ChiCC.2019.8865185

Meng XP , Pian ZY , Shen ZY , 2013 . Ant algorithm based on direction-coordinating . Contr Dec , 28 ( 5 ): 782 - 786 (in Chinese) . https://doi.org/10.13195/j.cd.2013.05.145.mengxp.017 https://doi.org/10.13195/j.cd.2013.05.145.mengxp.017

Nourinejad M , Roorda MJ , 2014 . A dynamic carsharing decision support system . Transp Res Part E Log Trans Rev , 66 : 36 - 50 . https://doi.org/10.1016/j.tre.2014.03.003 https://doi.org/10.1016/j.tre.2014.03.003

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 . https://doi.org/10.1016/j.tre.2011.07.001 https://doi.org/10.1016/j.tre.2011.07.001

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 . https://doi.org/10.1016/j.neucom.2020.02.126 https://doi.org/10.1016/j.neucom.2020.02.126

Solomon MM , 1987 . Algorithms for the vehicle routing and scheduling problems with time window constraints . Oper Res , 35 ( 2 ): 254 - 265 . https://doi.org/10.1287/opre.35.2.254 https://doi.org/10.1287/opre.35.2.254

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 . https://doi.org/10.1016/j.compeleceng.2022.107949 https://doi.org/10.1016/j.compeleceng.2022.107949

Wang WJ , 2010 . Improved genetic algorithm for vehicle routing problem with time windows . Int Conf on Intelligent Computing and Cognitive Informatics , p. 203 - 206 . https://doi.org/10.1109/ICICCI.2010.42 https://doi.org/10.1109/ICICCI.2010.42

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 . https://doi.org/10.1016/j.knosys.2018.07.024 https://doi.org/10.1016/j.knosys.2018.07.024

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 . https://doi.org/10.1016/j.eswa.2018.03.018 https://doi.org/10.1016/j.eswa.2018.03.018

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 . https://doi.org/10.1016/j.swevo.2020.100675 https://doi.org/10.1016/j.swevo.2020.100675

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 . https://doi.org/10.1016/j.eswa.2022.116690 https://doi.org/10.1016/j.eswa.2022.116690

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

Xiao RB , Wang YC , 2018 . Labour division in swarm intelligence for allocation problems: a survey . Int J Bio-Inspir Comput , 12 ( 2 ): 71 - 86 . https://doi.org/10.1504/IJBIC.2018.094186 https://doi.org/10.1504/IJBIC.2018.094186

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) . https://doi.org/10.3969/j.issn.1006-4869.2022.01.002 https://doi.org/10.3969/j.issn.1006-4869.2022.01.002

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) . https://doi.org/10.12011/1000-6788-2017-1328-13 https://doi.org/10.12011/1000-6788-2017-1328-13

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 . https://doi.org/10.1016/j.tre.2021.102545 https://doi.org/10.1016/j.tre.2021.102545

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 . https://doi.org/10.1504/IJWMC.2017.085567 https://doi.org/10.1504/IJWMC.2017.085567

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 . https://doi.org/10.1016/j.eswa.2019.113151 https://doi.org/10.1016/j.eswa.2019.113151

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 . https://doi.org/10.1631/FITEE.2100530 https://doi.org/10.1631/FITEE.2100530

Views

144

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰