This chapter describes an approach based on Monte Carlo Simulation (MCS) to solve the Capacitated Vehicle Routing Problem (CVRP) with route length restrictions and customer service times. The additional restriction introduces further challenges to the classical CVRP. The basic idea behind our approach is to combine direct MCS with an efficient heuristic, namely the Clarke and Wright Savings (CWS) algorithm, and a decomposition technique. The CWS heuristic provides a constructive methodology which is improved in two ways: (i) a special random behavior is introduced in the methodology using a geometric distribution; and (ii) a divide-and-conquer technique is used to decompose the original problem in smaller sub-problems that are easier to deal with. The method is tested using a set of well-known benchmarks. The chapter discusses the advantages and disadvantages of the proposed procedure in relation to other approaches for solving the same problem.
TopIntroduction
The Capacitated Vehicle Routing Problem (CVRP) is probably one of the most popular routing problems in Combinatorial Optimization. The objective is to find an ‘optimal’ set of routes for a fleet of homogeneous vehicles so that demands of a set of customers are satisfied. All routes begin and end at one or several depots, where all resources are initially located. Typically each vehicle has a maximum loading capacity, each customer is supplied by a single vehicle, and a vehicle cannot visit the same customer twice. Therefore, the objective function consists in minimizing total delivery costs, which are typically related to distances traveled by vehicles.
Known to be an NP-hard problem (Laporte and Semet 2001, Prins 2004), the CVRP has been studied for decades. Even so, it is still attracting a great amount of attention from researchers worldwide due to its potential applications, both in real-life scenarios situations as well as for the development of new algorithms, optimization methods and meta-heuristics for solving other combinatorial problems (Toth and Vigo 2002, Golden et al. 2008). Various approaches to the CVRP have been proposed during the past decades, ranging from the use of pure optimization methods such as linear programming –mainly used for solving small- to medium-size problems with relatively simple constraints–, to the use of heuristics and meta-heuristics that provide near-optimal solutions for medium and large-size problems with more complex constraints (Laporte 2007).
This chapter considers the CVRP with additional restrictions, in particular: (a) there is a route length restriction per vehicle, i.e., no route can exceed a given cost (assuming that cost is related to length), and (b) a service time restriction, which forms a part of a given tour’s duration, needs to be considered for each customer being served. This service time is usually transformed into a penalty cost per service that must also be added to the distance-based costs associated with each route.
All in all, the main goal of this chapter is threefold. First, it aims to illustrate the use of simulation-based heuristic approaches to deal with the CVRP with additional constraints such as those defined above. Second, it aims to show that simulation-based approaches can be competitive with existing heuristic approaches, in terms of the quality of the solutions obtained, in solving a combinatorial problem. Finally, it aims to highlight some interesting benefits that simulation-based approaches might offer.