An exact method for vehicle routing problem with backhaul discounts in urban express delivery network

The surge in e-commerce has led to an increased demand for urban express services, requiring the strategic development of delivery networks that are both efficient and cost-effective. This study addresses a practical vehicle routing problem (VRP) in an urban express delivery network to minimize tran...

Full description

Saved in:
Bibliographic Details
Published in:Cleaner Logistics and Supply Chain 2024-06, Vol.11, p.100157
Main Authors: Jinqiu Zhao, Yongwu Liu, Jinwei Zhang, Jing Zhang, Yixiao Huang, Le Yu, Binglei Xie
Format: Article
Language:English
Subjects:
Backhaul discounts
Branch-and-price algorithm
Multiple trips
Pickup and delivery
Vehicle routing
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The surge in e-commerce has led to an increased demand for urban express services, requiring the strategic development of delivery networks that are both efficient and cost-effective. This study addresses a practical vehicle routing problem (VRP) in an urban express delivery network to minimize transportation costs. Specifically, it considers the implementation of backhaul discounts, a factor disregarded in the existing literature. This VRP is further complicated by various realistic constraints, including pickup and delivery, time windows, multiple trips, heterogeneous fleets, and docking capacity limitations, which make most general VRP solvers inapplicable. This study proposes a trip-based formulation to overcome this challenge and develop a tailored branch-and-price algorithm. Feasible trips are classified into four types to simplify the computation of backhaul discounts, thereby enhancing solution efficiency. Validation with real-world data from SF Express substantiates the efficacy of our method and yields insights for sustainable city logistics management. Moreover, our simplified column generation algorithm exhibits competitive performance, achieving optimal solutions expeditiously for the tested instances.
ISSN:2772-3909
DOI:10.1016/j.clscn.2024.100157