Hongqi Li ^*, Xinyu Chang, Wencong Zhao, Yingrong Lu

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

Abstract：The rollon-rolloff vehicle routing problem (RRVRP) has drawn much attention of researchers due to the increasing concerns on waste material logistics. In literatures the RRVRP is formulated as the node routing problem with asymmetric arc cost and a maximum route length. In this paper we adopt the trip decomposition method to transfer the trip to arc demand so as to propose a vehicle flow formulation for the RRVRP. A two-stage heuristic involving the modified Clarke and Wright savings heuristic algorithm (CW) followed by a local search phase is developed to solve the formulation. The effectiveness of the proposed formulation and heuristic is demonstrated by computational experiments on randomly-generated small-scale instances and benchmark instances. 

Keywords: Routing; Rollon-rolloff; Vehicle flow formulation; Savings heuristic; Local search

1. Introduction

Waste management is a branch of green logistics and a key process in environment protection and resource conservation (Sbihi and Eglese, 2010). In literatures there are three basic types of vehicle routing problems (VRP) occurring in waste management (Bodin et al., 2000), of which the rollon-rolloff vehicle routing problem (RRVRP) has drawn much attention of researchers due to the increasing concerns on waste material logistics. 

The RRVRP considered in this paper is that presented by Bodin et al. (2000), which involves a single depot and a single disposal facility. Homogenous fleets of tractors are available at the depot. Each tractor begins and ends its route at the depot. Full containers sent from customers are emptied at the disposal facility. Customers require large-container level services, and tractors serve one customer at a time (Kim et al., 2006). Customer demand includes emptying a full container, ordering an empty container or changing a container. Time windows of customers are ignored. The constraint on the same maximum allowable operating time of tractors is respected. The objective is to find the number of tractors used and tractor routes that feature the minimum amount of total nonproductive (deadhead) time. Several variants of the RRVRP have been stated so far according to service types, number of depots and disposal facilities, time windows, etc. (Wy and Kim, 2013) For an overview of the RRVRP and the variants, we refer to Derigs et al. (2013), Wy et al. (2013), Wy and Kim (2013) and Li et al. (2016).