Pickup and Delivery Problem with Synchronous and Asynchronous Transshipment for Q-Commerce Delivery

Abstract

This study explores ways to improve delivery efficiency and reduce costs in the rapidly growing quick commerce (Q-commerce) market, which is expanding because of advancements in Internet of Things technology and the rise of contactless consumption. However, it faces significant challenges, such as high transportation costs and inefficient vehicle utilization. To address these challenges, a novel delivery system is proposed that simultaneously incorporates synchronous and asynchronous transshipment. The proposed system, the Pickup and Delivery Problem with two types of transshipment, is formulated as a mathematical optimization model. Since the problem is Nondeterministic Polynomial-time hard (NP-hard), implying that finding an optimal solution is computationally intensive as the problem scale increases, a two-phase heuristic algorithm is developed that combines adaptive large neighborhood search metaheuristic with transshipment scheduling. In Phase 1, adaptive large neighborhood search is employed to improve the initial Pickup and Delivery Problem solution. In Phase 2, the two transshipments are integrated into the improved solution. Experimental results from various scenarios show that the proposed two-phase algorithm effectively reduces Q-commerce delivery costs by approximately 10.97% compared with initial solutions. Of note, simultaneously considering synchronous and asynchronous transshipment resulted in an additional 0.5 percentage points (pp) improvement in the objective function value compared with using a single transshipment. These findings suggest that transshipment solutions can effectively reduce vehicle operating times and request travel distances, contributing to the future popularization of multi-echelon delivery systems.

Keywords

quick commerce pickup and delivery problem transshipment optimization adaptive large neighborhood search

Get full access to this article

View all access options for this article.

References

Lin

Zhou

Is on-Demand Same Day Package Delivery Service Green?

Transportation Research Part D: Transport and Environment, Vol. 61, 2018, pp. 118–139. https://doi.org/10.1016/j.trd.2017.06.016.

Allen

Piecyk

Cherrett

Juhari

M. N.

McLeod

Piotrowska

Bates

, et al. Understanding the Transport and CO2 Impacts of on-Demand Meal Deliveries: A London Case Study. Cities, Vol. 108, 2021, p. 102973. https://doi.org/10.1016/j.cities.2020.102973.

Lemardelé

Pinheiro Melo

Cerdas

Herrmann

Estrada

Life-Cycle Analysis of Last-Mile Parcel Delivery Using Autonomous Delivery Robots. Transportation Research Part D: Transport and Environment, Vol. 121, 2023, p. 103842. https://doi.org/10.1016/j.trd.2023.103842.

Zhu

Huang

The Meal Delivery Routing Problem in E-Commerce Platforms Under the Shared Logistics Mode. Journal of Theoretical and Applied Electronic Commerce Research, Vol. 18, No. 4, 2023, pp. 1799–1819. https://doi.org/10.3390/jtaer18040091.

Ouyang

Leung

E. K. H.

Huang

G. Q.

Community Logistics and Dynamic Community Partitioning: A New Approach for Solving E-Commerce Last Mile Delivery. European Journal of Operational Research, Vol. 307, No. 1, 2023, pp. 140–156. https://doi.org/10.1016/j.ejor.2022.08.029.

Puchinger

Sun

Van-Based Robot Hybrid Pickup and Delivery Routing Problem. European Journal of Operational Research, Vol. 298, No, 3, 2022, pp. 894–914. https://doi.org/10.1016/j.ejor.2021.06.009.

Cortés

C. E.

Matamala

Contardo

The Pickup and Delivery Problem with Transfers: Formulation and a Branch-and-Cut Solution Method. European Journal of Operational Research, Vol. 200, No. 3, 2010, pp. 711–724. https://doi.org/10.1016/j.ejor.2009.01.022.

Masson

Lehuédé

Péton

An Adaptive Large Neighborhood Search for the Pickup and Delivery Problem with Transfers. Transportation Science, Vol. 47, No. 3, 2013, pp. 344–355. https://doi.org/10.1287/trsc.1120.0432.

Zhang

Atasoy

Negenborn

R. R.

Preference-Based Multi-Objective Optimization for Synchromodal Transport Using Adaptive Large Neighborhood Search. Transportation Research Record: Journal of the Transportation Research Board, 2022. 2676: 71–87.

10.

Rais

Alvelos

Carvalho

M. S.

New Mixed Integer-Programming Model for the Pickup-and-Delivery Problem with Transshipment. European Journal of Operational Research, Vol. 235, No. 3, 2014, pp. 530–539. https://doi.org/10.1016/j.ejor.2013.10.038.

11.

Wolfinger

Salazar-González

J.-J.

The Pickup and Delivery Problem with Split Loads and Transshipments: A Branch-and-Cut Solution Approach. European Journal of Operational Research, Vol. 289, No. 2, 2021, pp. 470–484. https://doi.org/10.1016/j.ejor.2020.07.032.

12.

Wolfinger

A Large Neighborhood Search for the Pickup and Delivery Problem with Time Windows, Split Loads and Transshipments. Computers & Operations Research, Vol. 126, 2021, p. 105110. https://doi.org/10.1016/j.cor.2020.105110.

13.

Windras Mara

S. T.

Norcahyo

Jodiawan

Lusiantoro

Rifai

A. P.

A Survey of Adaptive Large Neighborhood Search Algorithms and Applications. Computers & Operations Research, Vol. 146, 2022, p. 105903. https://doi.org/10.1016/j.cor.2022.105903.

14.

Ropke

Pisinger

An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows. Transportation Science, Vol. 40, No. 4, 2006, pp. 455–472. https://doi.org/10.1287/trsc.1050.0135.

15.

Chow

J. Y. J.

The Pickup and Delivery Problem with Synchronized En-Route Transfers for Microtransit Planning. Transportation Research Part E: Logistics and Transportation Review, Vol. 157, 2022, p. 102562. https://doi.org/10.1016/j.tre.2021.102562.

16.

Chow

J. Y. J.

Dial-a-Ride Problem with Modular Platooning and En-Route Transfers. Transportation Research Part C: Emerging Technologies, Vol. 152, 2023, p. 104191. https://doi.org/10.1016/j.trc.2023.104191.

17.

Glover

Improved Linear Integer Programming Formulations of Nonlinear Integer Problems. Management Science, Vol. 22, No. 4, 1975, pp. 455–460. https://doi.org/10.1287/mnsc.22.4.455.