The Value of Preemptive Pick-Up Services in Dynamic Vehicle Routing for Last-Mile Delivery: Space-Time Network-Based Formulation and Solution Algorithms
In recent years, with the increase of emerging pick-up requests during service, logistics companies have been driven to integrate delivery and pick-up service in a dynamic environment. To provide a balanced and robust approach to cope with delivery requests and emerging pick-up requests, this articl...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2022-01-01
|
| Series: | Journal of Advanced Transportation |
| Online Access: | http://dx.doi.org/10.1155/2022/5052897 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832549716369342464 |
|---|---|
| author | Weiran Meng Lingyun Meng Guoshuai Han Xiaotian Zhuang Lu Carol Tong Shengnan Wu |
| author_facet | Weiran Meng Lingyun Meng Guoshuai Han Xiaotian Zhuang Lu Carol Tong Shengnan Wu |
| author_sort | Weiran Meng |
| collection | DOAJ |
| description | In recent years, with the increase of emerging pick-up requests during service, logistics companies have been driven to integrate delivery and pick-up service in a dynamic environment. To provide a balanced and robust approach to cope with delivery requests and emerging pick-up requests, this article aims at considering and modeling a practically useful service principle as preemptive services. To our knowledge, most existing studies assume that the dynamically arriving requests are handled in a non-preemptive processing sequence; that is, once the delivery person is allocated to a task, the process is noninterruptible till it gets completed. In the preemptive service, a service suspension of the delivery process (with low service utility) is allowed to satisfy the pick-up requests (with high service utility) first. To provide a systematic assessment on the value of preemptive service for evolving urban logistics systems, a dynamic vehicle routing problem with preemptive pick-up service (VRPPS) is proposed to systematically describe the problem with potentially complex dynamic priorities among different tasks. Based on a dynamically constructed space-time network, this study formulates a multicommodity flow model that aims at optimizing the generalized service utility and the operating cost simultaneously. To provide a fast value approximation, we present a solution framework deploying the augmented Lagrangian relaxation approach with embedded dynamic programming algorithms. This framework jointly integrates the processes of updating request information and obtaining optimal routes. Finally, the validity and effectiveness of the proposed methods are evaluated on an illustrative network and a real-world last-mile delivery network operated by a logistics company. |
| format | Article |
| id | doaj-art-5f966187fb824ad7ac881e7ea250e612 |
| institution | Kabale University |
| issn | 2042-3195 |
| language | English |
| publishDate | 2022-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Advanced Transportation |
| spelling | doaj-art-5f966187fb824ad7ac881e7ea250e6122025-02-03T06:08:45ZengWileyJournal of Advanced Transportation2042-31952022-01-01202210.1155/2022/5052897The Value of Preemptive Pick-Up Services in Dynamic Vehicle Routing for Last-Mile Delivery: Space-Time Network-Based Formulation and Solution AlgorithmsWeiran Meng0Lingyun Meng1Guoshuai Han2Xiaotian Zhuang3Lu Carol Tong4Shengnan Wu5School of Traffic and TransportationSchool of Traffic and TransportationSchool of Electronic and Information EngineeringDepartment of Intelligent Supply ChainResearch Institute of Frontier ScienceDepartment of Intelligent Supply ChainIn recent years, with the increase of emerging pick-up requests during service, logistics companies have been driven to integrate delivery and pick-up service in a dynamic environment. To provide a balanced and robust approach to cope with delivery requests and emerging pick-up requests, this article aims at considering and modeling a practically useful service principle as preemptive services. To our knowledge, most existing studies assume that the dynamically arriving requests are handled in a non-preemptive processing sequence; that is, once the delivery person is allocated to a task, the process is noninterruptible till it gets completed. In the preemptive service, a service suspension of the delivery process (with low service utility) is allowed to satisfy the pick-up requests (with high service utility) first. To provide a systematic assessment on the value of preemptive service for evolving urban logistics systems, a dynamic vehicle routing problem with preemptive pick-up service (VRPPS) is proposed to systematically describe the problem with potentially complex dynamic priorities among different tasks. Based on a dynamically constructed space-time network, this study formulates a multicommodity flow model that aims at optimizing the generalized service utility and the operating cost simultaneously. To provide a fast value approximation, we present a solution framework deploying the augmented Lagrangian relaxation approach with embedded dynamic programming algorithms. This framework jointly integrates the processes of updating request information and obtaining optimal routes. Finally, the validity and effectiveness of the proposed methods are evaluated on an illustrative network and a real-world last-mile delivery network operated by a logistics company.http://dx.doi.org/10.1155/2022/5052897 |
| spellingShingle | Weiran Meng Lingyun Meng Guoshuai Han Xiaotian Zhuang Lu Carol Tong Shengnan Wu The Value of Preemptive Pick-Up Services in Dynamic Vehicle Routing for Last-Mile Delivery: Space-Time Network-Based Formulation and Solution Algorithms Journal of Advanced Transportation |
| title | The Value of Preemptive Pick-Up Services in Dynamic Vehicle Routing for Last-Mile Delivery: Space-Time Network-Based Formulation and Solution Algorithms |
| title_full | The Value of Preemptive Pick-Up Services in Dynamic Vehicle Routing for Last-Mile Delivery: Space-Time Network-Based Formulation and Solution Algorithms |
| title_fullStr | The Value of Preemptive Pick-Up Services in Dynamic Vehicle Routing for Last-Mile Delivery: Space-Time Network-Based Formulation and Solution Algorithms |
| title_full_unstemmed | The Value of Preemptive Pick-Up Services in Dynamic Vehicle Routing for Last-Mile Delivery: Space-Time Network-Based Formulation and Solution Algorithms |
| title_short | The Value of Preemptive Pick-Up Services in Dynamic Vehicle Routing for Last-Mile Delivery: Space-Time Network-Based Formulation and Solution Algorithms |
| title_sort | value of preemptive pick up services in dynamic vehicle routing for last mile delivery space time network based formulation and solution algorithms |
| url | http://dx.doi.org/10.1155/2022/5052897 |
| work_keys_str_mv | AT weiranmeng thevalueofpreemptivepickupservicesindynamicvehicleroutingforlastmiledeliveryspacetimenetworkbasedformulationandsolutionalgorithms AT lingyunmeng thevalueofpreemptivepickupservicesindynamicvehicleroutingforlastmiledeliveryspacetimenetworkbasedformulationandsolutionalgorithms AT guoshuaihan thevalueofpreemptivepickupservicesindynamicvehicleroutingforlastmiledeliveryspacetimenetworkbasedformulationandsolutionalgorithms AT xiaotianzhuang thevalueofpreemptivepickupservicesindynamicvehicleroutingforlastmiledeliveryspacetimenetworkbasedformulationandsolutionalgorithms AT lucaroltong thevalueofpreemptivepickupservicesindynamicvehicleroutingforlastmiledeliveryspacetimenetworkbasedformulationandsolutionalgorithms AT shengnanwu thevalueofpreemptivepickupservicesindynamicvehicleroutingforlastmiledeliveryspacetimenetworkbasedformulationandsolutionalgorithms AT weiranmeng valueofpreemptivepickupservicesindynamicvehicleroutingforlastmiledeliveryspacetimenetworkbasedformulationandsolutionalgorithms AT lingyunmeng valueofpreemptivepickupservicesindynamicvehicleroutingforlastmiledeliveryspacetimenetworkbasedformulationandsolutionalgorithms AT guoshuaihan valueofpreemptivepickupservicesindynamicvehicleroutingforlastmiledeliveryspacetimenetworkbasedformulationandsolutionalgorithms AT xiaotianzhuang valueofpreemptivepickupservicesindynamicvehicleroutingforlastmiledeliveryspacetimenetworkbasedformulationandsolutionalgorithms AT lucaroltong valueofpreemptivepickupservicesindynamicvehicleroutingforlastmiledeliveryspacetimenetworkbasedformulationandsolutionalgorithms AT shengnanwu valueofpreemptivepickupservicesindynamicvehicleroutingforlastmiledeliveryspacetimenetworkbasedformulationandsolutionalgorithms |