A divide-and-conquer strategy for the vehicle routing problem

Solving the vehicle routing problem is vital for distribution and transportation businesses needing to ensure timely distribution and minimise costs. The multivehicle routing problem is a complex variation involving multiple vehicles and numerous destinations for goods. Jiaqi Li, a graduate student at The University of Hong Kong, Yun Wang at Zhejiang Sci-Tech University, China, and Professor Ke-Lin Du at Concordia University, Canada, have vanquished this problem. The researchers have developed a new, improved genetic algorithm as a mathematical solution – with a novel ‘divide-and-conquer’ strategy inspired by dynamic programming.

For optimal vehicle routing, ensuring timely distribution and reducing the cost of logistics (accurately delivering goods from the supplier to the customer) is crucial to the viability of distribution and transportation businesses. It was initially investigated by G B Dantzig and J H Ramser in 1959 and is known as ‘The Truck Dispatching Problem’. Behind this classical vehicle routing problem (VRP) is the need to uncover the optimal routes for a fleet of vehicles delivering to multiple locations, at the least possible cost to the distributor. It is relatively easy to understand the VRP; solving it is another matter.

There is a more complex variation of the VRP called the multivehicle routing problem (MVRP). Solutions for the MVRP must factor in a fleet of vehicles delivering to a myriad of customers while also considering traveling-time delays arising from traffic congestion. All this must be achieved at the lowest cost. Fortunately, three researchers – Jiaqi Li, a graduate student at The University of Hong Kong, and colleagues Yun Wang from Zhejiang Sci-Tech University, China, and Professor Ke-Lin Du from Concordia University, Montreal, Canada – have defeated the conundrum with an innovative mathematical solution inspired by dynamic programming.

The vehicle routing problem

The VRP is a generalisation of the travelling salesperson problem, a classic optimisation problem that has been examined since the 1930s. It is based on a scenario where a salesperson must visit several cities. Their journey must finish back where they started, and they can visit each location only once. They can visit the cities in any order, but they need to travel the least possible distance. The problem is modelled as a network, with the cities represented by nodes and connected by paths weighted in terms of the time or distance required to travel between two cities.

The VRP is a combinatorial integer programming problem. It involves minimising the total route cost and establishing the maximum number of stops each vehicle can make while keeping operating costs to a minimum. It considers factors such as the number of vehicles, vehicle capacity, time constraints, location of customers, order priority, speed limits, and traffic patterns.

The VRP is traditionally solved using metaheuristics – strategies to guide the search process to find optimal or near-optimal solutions – in the form of an evolutionary or genetic algorithm (GA). GAs mimic biological evolution to solve optimisation problems. Using a natural selection process, the genetic algorithm repeatedly modifies a group of solutions. The VRP is an NP (nondeterministic polynomial time) Problem and is said to be NP-hard, so it is ‘at least as hard as any NP Problem’. That means an algorithm used to solve the VRP can be translated and used to solve any NP Problem.

The multivehicle routing problem

The MVRP extends the VRP to include mixed-fleet vehicles with time windows (specific time slots when visits must be made). Fleets can consist of any combination of vehicles using traditional fuel, electric vehicles, and plug-in hybrids. The goal of the MVRP is to discover a set of routes that multiple vehicles can use to serve numerous customers, which keeps total costs to a minimum but still takes traffic delays into account.

Now researchers have developed a new mathematical model to solve the MVRP using an improved genetic algorithm with a novel ‘divide-and-conquer’ strategy. Inspired by dynamic programming, Li, Wang, and Du propose an distribution path optimisation method with two stages: a distribution sequence search and a distribution path search.

Vanquishing the MVRP

The objective of the researchers’ proposed model is to find the shortest possible route requiring the least number of vehicles while keeping costs to a minimum. Multiple vehicles are being used to distribute products to multiple demand nodes, so the optimal number of vehicles required and the route for each vehicle will have to be determined.

This is modelled with two objective functions (mathematical expressions whose values must be either maximised or minimised according to constraints). The first objective function involves minimising the total cost. The second objective function minimises the total length of the route. These are subject to the following constraints: a vehicle’s maximum load capacity cannot be exceeded; only one vehicle can fulfil a delivery at any node; all distribution jobs are completed by the assigned number of vehicles; only one vehicle can arrive or depart from a demand node; and, finally, there are no loops or duplicated sections within the optimised path or distribution sequence.

Divide-and-conquer strategy

When creating their new divide-and-conquer strategy, the researchers were inspired by dynamic programming, where an optimisation problem is broken down into simpler sub-problems. When there are a lot of demand nodes and road intersections, the problem is NP-hard, and it isn’t easy to uncover an optimal route. Instead, Li and colleagues break the problem into smaller sub-problems that they solve recursively. Initially, they find an optimal sequence of demand nodes. Then, using their improved genetic algorithm, they search for an optimal route between any two of the nodes and build the complete route step by step.

An improved genetic algorithm

Each solution in a genetic algorithm is referred to as an ‘individual’ and coded like a chromosome. A group of individuals form a ‘population’. Here, an individual is a route between two nodes. Individuals are selected from the population using a combination of roulette wheel selection and an elitist strategy. A roulette wheel is constructed based on each individual’s relative ‘fitness’ to select the individuals for the next generation – or population. Elitist selection retains the individuals with the best fitness values for the next generation. Selected individuals form a new population, and the process is repeated for all paths between nodes for a vehicle’s complete route. This process is repeated to find optimal distribution paths for each of the remaining vehicles.

Real-life application

The researchers verify the rationality and feasibility of their model with a simulation using data from a manufacturer in Hangzhou, China. The manufacturer delivers products to 40 customers. Analysing the results revealed that the new, improved genetic algorithm – employing the divide-and-conquer approach – converged on the optimal solution quicker than the traditional, simple genetic algorithm. Moreover, the improved genetic algorithm outperformed the traditional genetic algorithm for route feasibility, route topology, and total cost.

The researchers’ new methodology for solving the MVRP can help to reduce the overall cost of a fast and convenient distribution service. In addition to increasing logistics efficiency for manufacturers, distributors, and transport companies, Li and his colleagues’ model can be useful for other applications, such as optimising manufacturing flow–shop scheduling.