Solution methods for some variants of the vehicle routing problem

Abstract

The Vehicle Routing Problem (VRP) is among the most important and widely researched problems in the field of combinatorial optimization. It fits a large variety of applications across many industries faced with the logistics problem of distribution and collection of goods. Depending on the needs of the specific industry, a collection of variants with different properties can be found in the literature. Here we introduce two specific variants of the classical VRP. Then we develop both exact and heuristic solution methods to solve the problems.

Firstly, we introduce a problem motivated by a company that runs a large distribution network in a city in Ecuador. The company operates with a set of trucks and a set of sellers that are routed simultaneously, and a set of retailers that must be visited.

The routing is performed in two stages over the course of one week. The sellers visit every retailer exactly once and take their orders. Precisely on the following day, the trucks visit the retailers and deliver the goods. The aim is to find a starting point for the sellers, spread the deliveries evenly across a planning horizon and balance the routes to guarantee fair pay for the employees while minimising the travelling cost.

We propose two mixed-integer models and a branch-and-cut algorithm along with new valid inequalities for routing problems with an unknown depot location.

Due to the time and memory limitations of the exact approach, to solve this company’s large-scale problem, we developed a heuristic procedure within a tabu search framework. In the construction phase, we introduce an innovative cluster-first route-second heuristic using a combination of proposed alterations of the k-means clustering procedure. A random cheapest insertion routing procedure is applied to each of the clusters. This is an efficient and robust algorithmthat can be applied to different VRP variants. For the improvement phase of the heuristic we use short-term memory and intra-day improvements, followed by diversification with inter-day improvements and intensification on the best-known routes. Through extensive computational analysis we prove the efficiency of the outlined solutionmethods. To the best of our knowledge this problem is new in the literature.

Finally, we present a case study for a capacitated multi-trip VRP with depot location, fleet sizing and time windows. In the first stage, depots are allocated by solving a p-median problem and fleet sizes are determined by identifying the vehicle requirements of several worst-case demand instances. The second stage consists of optimizing the vehicle routes on a daily basis to satisfy the fluctuating customer demand. We assign customers to depots based on distance and routing effort. For the routing problem, we combine a branch-and-cut algorithm and a heuristic with a route construction phase and packing of routes into vehicle trips. This solution approach is a published joint work and the winner of the 12th MOPTA competition.