A Multi-Strategy ALNS for the VRP with Flexible Time Windows and Delivery Locations
With the rapid development of e-commerce, the importance of logistics distribution is becoming increasingly prominent. In particular, the last-mile delivery is particularly important because it serves customers directly. Improving customer satisfaction is one of the important factors to ensure the q...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-04-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/15/9/4995 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850278804372586496 |
|---|---|
| author | Xiaomei Zhang Xinchen Dai Ping Lou Jianmin Hu |
| author_facet | Xiaomei Zhang Xinchen Dai Ping Lou Jianmin Hu |
| author_sort | Xiaomei Zhang |
| collection | DOAJ |
| description | With the rapid development of e-commerce, the importance of logistics distribution is becoming increasingly prominent. In particular, the last-mile delivery is particularly important because it serves customers directly. Improving customer satisfaction is one of the important factors to ensure the quality of service in delivery and also an important guarantee for improving the market competitiveness of logistics enterprises. In the process of last-mile delivery, flexible delivery locations and variable delivery times are effective means to improve customer satisfaction. Therefore, this paper introduces a Vehicle Routing Problem with flexible time windows and delivery locations, considering customer satisfaction (VRP-CS), which considers customer satisfaction by using prospect theory from two aspects: the flexibility of delivery time and delivery locations. This VRP-CS is formally modeled as a bi-objective optimization problem, which is an NP-hard problem. To solve this problem, a Multi-Strategy Adaptive Large Neighborhood Search (MSALNS) method is proposed. Operators guided by strategies such as backtracking and correlation are introduced to create different neighborhoods for ALNS, thereby enriching search diversity. In addition, an acceptance criterion inspired by simulated annealing is designed to balance exploration and exploitation, helping the algorithm avoid being trapped in local optima. Extensive numerical experiments on generated benchmark instances demonstrate the effectiveness of the VRP-CS model and the efficiency of the proposed MSALNS algorithm. The experiment results on the generated benchmark instances show that the total cost of the VRP-CS is reduced by an average of 14.22% when optional delivery locations are utilized compared to scenarios with single delivery locations. |
| format | Article |
| id | doaj-art-e205293e510d4c79ae9662c65d1f7ff6 |
| institution | OA Journals |
| issn | 2076-3417 |
| language | English |
| publishDate | 2025-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj-art-e205293e510d4c79ae9662c65d1f7ff62025-08-20T01:49:20ZengMDPI AGApplied Sciences2076-34172025-04-01159499510.3390/app15094995A Multi-Strategy ALNS for the VRP with Flexible Time Windows and Delivery LocationsXiaomei Zhang0Xinchen Dai1Ping Lou2Jianmin Hu3School of Information Engineering, Wuhan University of Technology, Wuhan 430070, ChinaSchool of Information Engineering, Wuhan University of Technology, Wuhan 430070, ChinaSchool of Information Engineering, Wuhan University of Technology, Wuhan 430070, ChinaSchool of Information Engineering, Hubei University of Economics, Wuhan 430205, ChinaWith the rapid development of e-commerce, the importance of logistics distribution is becoming increasingly prominent. In particular, the last-mile delivery is particularly important because it serves customers directly. Improving customer satisfaction is one of the important factors to ensure the quality of service in delivery and also an important guarantee for improving the market competitiveness of logistics enterprises. In the process of last-mile delivery, flexible delivery locations and variable delivery times are effective means to improve customer satisfaction. Therefore, this paper introduces a Vehicle Routing Problem with flexible time windows and delivery locations, considering customer satisfaction (VRP-CS), which considers customer satisfaction by using prospect theory from two aspects: the flexibility of delivery time and delivery locations. This VRP-CS is formally modeled as a bi-objective optimization problem, which is an NP-hard problem. To solve this problem, a Multi-Strategy Adaptive Large Neighborhood Search (MSALNS) method is proposed. Operators guided by strategies such as backtracking and correlation are introduced to create different neighborhoods for ALNS, thereby enriching search diversity. In addition, an acceptance criterion inspired by simulated annealing is designed to balance exploration and exploitation, helping the algorithm avoid being trapped in local optima. Extensive numerical experiments on generated benchmark instances demonstrate the effectiveness of the VRP-CS model and the efficiency of the proposed MSALNS algorithm. The experiment results on the generated benchmark instances show that the total cost of the VRP-CS is reduced by an average of 14.22% when optional delivery locations are utilized compared to scenarios with single delivery locations.https://www.mdpi.com/2076-3417/15/9/4995vehicle routing problemdelivery optionstime windowcustomer satisfactionadaptive large neighborhood search |
| spellingShingle | Xiaomei Zhang Xinchen Dai Ping Lou Jianmin Hu A Multi-Strategy ALNS for the VRP with Flexible Time Windows and Delivery Locations Applied Sciences vehicle routing problem delivery options time window customer satisfaction adaptive large neighborhood search |
| title | A Multi-Strategy ALNS for the VRP with Flexible Time Windows and Delivery Locations |
| title_full | A Multi-Strategy ALNS for the VRP with Flexible Time Windows and Delivery Locations |
| title_fullStr | A Multi-Strategy ALNS for the VRP with Flexible Time Windows and Delivery Locations |
| title_full_unstemmed | A Multi-Strategy ALNS for the VRP with Flexible Time Windows and Delivery Locations |
| title_short | A Multi-Strategy ALNS for the VRP with Flexible Time Windows and Delivery Locations |
| title_sort | multi strategy alns for the vrp with flexible time windows and delivery locations |
| topic | vehicle routing problem delivery options time window customer satisfaction adaptive large neighborhood search |
| url | https://www.mdpi.com/2076-3417/15/9/4995 |
| work_keys_str_mv | AT xiaomeizhang amultistrategyalnsforthevrpwithflexibletimewindowsanddeliverylocations AT xinchendai amultistrategyalnsforthevrpwithflexibletimewindowsanddeliverylocations AT pinglou amultistrategyalnsforthevrpwithflexibletimewindowsanddeliverylocations AT jianminhu amultistrategyalnsforthevrpwithflexibletimewindowsanddeliverylocations AT xiaomeizhang multistrategyalnsforthevrpwithflexibletimewindowsanddeliverylocations AT xinchendai multistrategyalnsforthevrpwithflexibletimewindowsanddeliverylocations AT pinglou multistrategyalnsforthevrpwithflexibletimewindowsanddeliverylocations AT jianminhu multistrategyalnsforthevrpwithflexibletimewindowsanddeliverylocations |