Hongqi Li ^*, Lu Zhang, Tan Lv, Xinyu Chang

School of Transportation Science and Engineering, BeiHang University. No. 37 Xueyuan Road, Haidian District, Beijing, 100191, China

* Corresponding author. E-mail addresses: lihongqi@buaa.edu.cn

Abstract

Most of the studies address issues relating to the delivery from satellites to customers, which is throughout the end part of the linehaul-delivery system. Differing from the long-term strategic problems including the two-echelon vehicle routing problem (2E-VRP), the two-echelon location routing problem (2E-LRP) and the truck and trailer routing problem (TTRP) which make location decisions in depots or satellites, the paper introduces a short-term tactical problem named the two-echelon time-constrained vehicle routing problem in linehaul-delivery systems (2E-TVRP) that does not involve location decisions. The linehaul level and the delivery level are linked through city distribution centers (CDCs) located on the outskirts of cities. The 2E-TVRP has inter-CDC linehaul on the first level and urban delivery from CDCs to satellites on the second level. Vehicle routes on different levels are interacted by time constraints. A mixed integer nonlinear programming model for the 2E-TVRP is put forward, and a mixed integer linear programming model is used as the benchmark model. The Clarke and Wright savings heuristic algorithm (CW) improved by a local search phase is adopted. The 2E-TVRP formulations and the heuristic algorithm are tested by using 140 randomly-generated instances with up to 10 CDCs and 500 satellites. The computational results indicate that the heuristic can effectively solve various instances of the 2E-TVRP. 

Keywords: Routing; Two-echelon; Linehaul-delivery system; Time-constrained; Mixed integer programming model; Heuristic

Introduction

The vehicle routing problem (VRP), which has been studied extensively in the literature (for an overview of the VRP, we refer to Laporte (2009)), can be used as a principal tool for planning the operations of city logistics schemes (van Duin et al., 2007). Large amounts of cargoes are transported to and from the outside of a city via linehaul vehicles that are often inappropriate or forbidden for the delivery inside a city. Cargo transshipments between linehaul vehicles and delivery vehicles are necessary. In two-echelon city logistics systems in literature (Crainic et al., 2009), the first level involves vehicles delivering cargoes from the city distribution centers (CDCs) located on the outskirts of cities to satellites, and the second level involves vehicles performing the satellite-to-customer delivery routes. The two-echelon vehicle routing problem (2E-VRP), the two-echelon location routing problem (2E-LRP) and the truck and trailer routing problem (TTRP) are useful to plan the operations of two-echelon city logistics systems.