Hongqi Li ^*, Tan Lv, Yanran Li

Schoolof 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

The tractor and semitrailer routing problem with many-to-many demand (TSRP-MMD) is investigated in this study. The TSRP-MMD extends the existing studies on the rollon-rolloff vehicle routing problem (RRVRP) to a many-to-many problem with an intercity line-haul network background. To demonstrate and utilize the energy efficiency of the tractor and semitrailer combination, the TSRP-MMD takes carbon dioxide (CO₂)emissions per ton-kilometer as the objective. Because the problem is NP-hard, a modified Clarke and Wright Savings heuristic algorithm(CW) followed by an improvement phase and a local search phase is developed to solve the TSRP-MMD. The integer program is used to find optimum solutions for small-scale problems. The computational results show that the developed heuristics can be efficiently used to solve the problem.

Keywords: Tractor and semitrailer routing problem; Carbon dioxide (CO₂) emissions; Heuristics

1. Introduction

In two-tiered city logistics systems (Crainic et al., 2009), the first tier involves vehicles delivering freight from the city distribution centers (CDCs) located on the outskirts of the city to satellites facilities, and the second tier involves vehicles performing the satellite-to-customer delivery routes. Given the concerns regarding the impact of city infrastructure (e.g., roads, locations of satellite facilities) on freight delivery, small-capacity vehicles are allowed. The vehicle routing problem (VRP) can be used as a principal tool for planning the operations of many types of city logistics schemes (van Duin et al., 2007). The traditional VRP can provide route optimization measures for city logistics. A VRP considering load factor controls and cooperative delivery can provide measures on emission mitigation in city logistics. The VRP combined with the location problem can provide optimal locations of city logistics terminals or depots. Because small-capacity vehicles are practically permitted in city logistics systems, the VRP generally focuses on the route optimization of small-capacity vehicles.

As a type of intermediary facility of city logistics systems, a CDC is not the origin of freight. There is an intercity line-haul tier that involves large-capacity vehicles transporting freight among CDCs of various cities. Unlike other related problems, such as the VRP or the Traveling Salesman Problem (TSP), which are considered one-to-many problems (Barcos et al., 2010), the type of problem considered in the line-haul tier resembles a many-to-many problem, where shipping from original CDCs to terminal CDCs and each CDC act simultaneously as origin and destination. The bulk transportation of large volumes of freight between CDCs allows economies of scale to be achieved, thus lowering intercity shipping costs. At intermediary facilities of city logistics systems such as CDCs, large-capacity vehicles are transferred to small-capacity vehicles.