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

Abstract

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.

Keywords

• Vehicle routing
• Backhaul discounts
• Pickup and delivery
• Multiple trips
• Branch-and-price algorithm