Full Text:   <780>

Summary:  <226>

Suppl. Mater.: 

CLC number: TP399

On-line Access: 2023-07-24

Received: 2022-11-21

Revision Accepted: 2023-04-06

Crosschecked: 2023-07-24

Cited: 0

Clicked: 664

Citations:  Bibtex RefMan EndNote GB/T7714

 ORCID:

Ren-bin Xiao

https://orcid.org/0000-0003-0951-2734

Zhenhui FENG

https://orcid.org/0000-0001-7004-8868

-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2023 Vol.24 No.7 P.1062-1079

http://doi.org/10.1631/FITEE.2200585


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


Author(s):  Zhenhui FENG, Renbin XIAO

Affiliation(s):  School of Artificial Intelligence and Automation, Huazhong University of Science and Technology,Wuhan 430074,China; more

Corresponding email(s):   feng_zh@hust.edu.cn, rbxiao@hust.edu.cn

Key Words:  Vehicle routing problem with constraints (VRPC), Spatiotemporal distance function, Labor division strategy, Ant colony algorithm (ACO


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.

@article{title="Spatiotemporal distance embedded hybrid ant colony algorithm for a kind of vehicle routing problem with constraints",
author="Zhenhui FENG, Renbin XIAO",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="24",
number="7",
pages="1062-1079",
year="2023",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.2200585"
}

%0 Journal Article
%T Spatiotemporal distance embedded hybrid ant colony algorithm for a kind of vehicle routing problem with constraints
%A Zhenhui FENG
%A Renbin XIAO
%J Frontiers of Information Technology & Electronic Engineering
%V 24
%N 7
%P 1062-1079
%@ 2095-9184
%D 2023
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.2200585

TY - JOUR
T1 - Spatiotemporal distance embedded hybrid ant colony algorithm for a kind of vehicle routing problem with constraints
A1 - Zhenhui FENG
A1 - Renbin XIAO
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 24
IS - 7
SP - 1062
EP - 1079
%@ 2095-9184
Y1 - 2023
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.2200585


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

关键词:受限车辆路径问题;时空距离函数;劳动分工策略;蚁群算法

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

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

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2024 Journal of Zhejiang University-SCIENCE