The generalized rollon-rolloff vehicle routing problem and savings-based algorithm
Hongqi Li a *, Xiaorong Jiana, Xinyu Changb, Yingrong Lua, c
aSchool of Transportation Science and Engineering, Beihang University. No. 37 Xueyuan Road, Haidian District, Beijing, 100191, China
bChina Academy of Transportation Sciences. No. 240 Huixinli, Chaoyang District, Beijing, 100029, China
cBeijing Key Laboratory for Cooperative Vehicle Infrastructure System and Safety Control, Beihang University. No. 37 Xueyuan Road, Haidian District, Beijing, 100191, China
* Corresponding author.E-mail addresses: lihongqi@buaa.edu.cn
Abstract
Taking the waste collection management as the practical background, the rollon-rolloff vehicle routing problem (RRVRP) involves tractors pulling large containers between customer locations and the disposal facility. Each used-tractor begins and ends its route at the depot. Customer demand includes emptying a full container, ordering an empty container or changing a container. The objective is to find tractor routes that feature the minimum amount of total nonproductive time. In the literature the RRVRP is formulated as the node routing problem, and the “trip” definition that is the complete transport service of a container is used. To relax some assumptions of the RRVRP to cater to practical desires, we present a variant called the generalized RRVRP (G-RRVRP). The G-RRVRP generalizes the practical background,the objective function and the demand flow, and considers specially container loading and unloading time constraints. The G-RRVRP classifies demand into loaded-container demand and cargo demand with time windows. On condition of respecting container loading/unloading time and customer time windows, the G-RRVRP can design tractor routes for the synchronous scheduling of loaded and empty containersso as to ensure the timeliness of transport service. The G-RRVRP aims to minimizethe total running cost ofused tractors, instead of the total nonproductive time of tractors adopted by the RRVRP. A mixed integer linear programming model for the G-RRVRPis proposed. The Benders decomposition algorithm involving Pareto-optimal cuts and Benders decomposition-callback implementation, and a two-stage heuristicinvolving the savings algorithm followed by a local search phase are provided. The mathematical formulation and the two-stage heuristic are tested by solving 40 small-scale instances and 20 benchmark instances. Small-scale instances can be solved directly by CPLEX through the Benders decomposition strategies to find exact solutions. The case study indicates the applicability of the G-RRVRP model and thetwo-stageheuristic to realistic-size problems abstracted from intercity linehaul systems. The computational experiments and case study indicate that the heuristic can solve various instances of the G-RRVRP such that the solution quality and the computation time are acceptable.
Keywords: Rollon-rolloff vehicle routing problem; Generalized RRVRP;Mixed integer linear programming;Benders decomposition; Savings algorithm
1. Introduction
So farresearchers have put forward several kinds of vehicle routing problems (VRPs) catering to waste collection management, one of which is the rollon-rolloff vehicle routing problem (RRVRP). The basic form of the RRVRP was presented by Bodin et al. (2000). The RRVRP involves one depot for holding tractors and one disposal facility for emptying full-containers. Each used-tractor begins and ends its route at the depot. Customer demand includes emptying a full container, ordering an empty container or replacing a full container with an empty container. Tractors pull large containers between customer locations and the disposal facility. Tractorscan only move one container to serve one customer at a time (Kim et al., 2006). The objective is to find tractor routes that feature the minimum of total nonproductive time.In nonproductive time tractors run alone on arcs.
The waste collection management is the practical background of the RRVRP. Formulating the RRVRP as the node routing problem, Bodin et al. (2000) presented the RRVRP on a directed complete graph G=(V, A). Ais the arc set. Vis the vertex set that consists of one depot, one disposal facility which is also regarded as an unlimited inventory of empty containers, and an amount of customer locations. Customer demand is classified into several types of trips served by tractors. A “trip” is defined to be the complete service of a container for a customer. Four types of trips (i.e., Type 1, Type 2, Type 3, and Type 4) are defined in the RRVRP stated by Bodin et al. (2000). For the Type 1, a full container is transported by a tractor from a customer to the disposal facility for emptying, and the emptied container is returned to the customer by the same tractor. For the Type 2, an empty container is exchanged with a full container at a customer location. For the Type 3, an empty container is brought to a customer. For the Type 4, a full container from a customer is transferred to the disposal facility. The service time of a trip includes container loading/unloading time and traveling time. The loaded container leg and the empty container leg are integrated in the first or the second type of trips.
In the literature several variants of the RRVRP have been proposed, which are characterized by the involved service types, time windows, etc. De Meulemeester et al. (1997) solved a variant associated with the collection and delivery of skips. A tractor can carry only one skip at a time. In one skip a tractor departing from a depot transports a full container from a customer location to a disposal site. Bodin et al. (2000) solved the RRVRP throughseveral heuristics, and twenty benchmark instances ranging from 50 to 199 trips and belonging to four classes (i.e., class A, B, C, or D) were used. In each class there are five test problems. The four classes differ in the mix of Type 1, Type 2, Type 3, and Type 4 trips. The number of trips in the five test problems in each class is 50, 75, 100, 150, and 199 trips, respectively. The class A problems have a preponderance of Type 1 trips, the class B problems have about the same number of Type 1 and Type 2 trips, and the class C problems have a preponderance of Type 2 trips. All class A, class B, and class C problems have only a few Type 3 and Type 4 trips. The class D problems have about the same number of Type 1, Type 2, Type 3, and Type 4 trips. Derigs et al. (2013) combined local search and large neighborhood search to solve the twenty benchmark instances provided by Bodin et al. (2000). Wy and Kim (2013) adopted a large neighborhood search and various improvement methods to solve the RRVRP. New best-known solutions are found for seventeen instances out of the twenty benchmark instances of Bodin et al. (2000). Baldacci et al. (2006) proposed the multiple disposal facilities and multiple inventory locations RRVRP (M-RRVRP). Five types of trips are considered. A bounding procedure combining three lower bounds derived from different relaxations of the M-RRVRP formulation is provided.Wy et al. (2013) presented the RRVRP with time windows (RRVRPTW) considering multiple disposal facilities and multiple inventory locations. Hauge et al. (2014) addressed another type of the RRVRP in which four types of trips, multiple depots, multiple disposal facilities and various container types are considered.