See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/366669859

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

Article in Research Outreach · December 2022

DOI: 10.32907/RO-133-37011672744

CITATIONS READS

0 77

3 authors, including:

Jiaqi Li Ke-Lin Du
The University of Hong Kong Xonlink Inc
2 PUBLICATIONS 1 CITATION 143 PUBLICATIONS 3,049 CITATIONS

SEE PROFILE SEE PROFILE

All content following this page was uploaded by Ke-Lin Du on 26 February 2023.

The user has requested enhancement of the downloaded file.

 Jiaqi Li
E: jucky@connect.hku.hk T: +852 6672 1022

A divide-and-conquer strategy
for the vehicle routing problem
Research Objectives References
Li, Wang, and Du have worked out how to efficiently Li, J, Wang, Y, Du, K-L, (2022) Distribution path optimization by
distribute goods from manufacturers’ distribution nodes to an improved genetic algorithm combined with a divide-and-
retailers’ demand nodes at the lowest cost possible. conquer strategy. Technologies, 10(4), 81. www.doi.org/10.3390/
technologies10040081

Detail Dantzig, GB, Ramser, JH, (1959) The Truck Dispatching Problem.
Management Science, 6(1), 80–91. www.doi.org/10.1287/
Address mnsc.6.1.80
Flat D, 13th Floor, Block C,
Chong Yip Centre,
423-425 Queen’s Road West,
Personal Response
Hong Kong
What inspired you to develop the divide-and-
conquer strategy?
Bio
Jiaqi Li has a BSc degree in mechanical engineering and The divide-and-conquer strategy is the spotlight of our
work. When we investigated route planning on a map, we
is a graduate student in the Faculty of Engineering at The
found that for two locations in a large region there may be tens
University of Hong Kong. of thousands of nodes for route planning, and it is impossible
to find an optimal or suboptimal route. For example, if we plan
Yun Wang is a faculty member at Zhejiang University, China. a route from a location in Hangzhou to a location in Beijing (a
distance of over 1,000 kilometres), there are tens or hundreds
of thousands of road intersections between the two locations;
Professor Ke-Lin Du is an associate professor at Concordia
no matter what metaheuristics are used, it is impossible to
University, Canada. make the route planner practical. We therefore designed
the divide-and-conquer strategy, inspired by dynamic
Funding programming, to speed up a metaheuristic to effectively solve
The National Natural Science Foundation of China (Grant the problem.
number: 51475434). What are the next steps before your model is ready for
real-world use?
The divide-and-conquer strategy is practical, not
patented, and it can be used by anyone in their real-
world applications. 
Engineering & Technology︱Jiaqi Li

A divide-and-conquer
strategy for the vehicle
routing problem
F
Solving the vehicle routing or optimal vehicle routing, ensuring THE VEHICLE ROUTING PROBLEM
problem is vital for distribution timely distribution and reducing the The VRP is a generalisation of the
and transportation businesses cost of logistics (accurately delivering travelling salesperson problem, a classic
needing to ensure timely goods from the supplier to the customer) optimisation problem that has been
distribution and minimise is crucial to the viability of distribution examined since the 1930s. It is based on
costs. The multivehicle routing and transportation businesses. It was a scenario where a salesperson must visit
problem is a complex variation initially investigated by G B Dantzig and several cities. Their journey must finish
involving multiple vehicles J H Ramser in 1959 and is known as ‘The back where they started, and they can
and numerous destinations Truck Dispatching Problem’. Behind visit each location only once. They can
for goods. Jiaqi Li, a graduate this classical vehicle routing problem visit the cities in any order, but they need
student at The University of (VRP) is the need to uncover the optimal to travel the least possible distance. The
Hong Kong, Yun Wang at routes for a fleet of vehicles delivering to problem is modelled as a network, with
Zhejiang Sci-Tech University, multiple locations, at the least possible the cities represented by nodes and
China, and Professor Ke-Lin Du cost to the distributor. It is relatively connected by paths weighted in terms
at Concordia University, Canada, easy to understand the VRP; solving it is of the time or distance required to travel
have vanquished this problem. another matter. between two cities.
The researchers have developed
a new, improved genetic There is a more complex variation of The VRP is a combinatorial integer
algorithm as a mathematical the VRP called the multivehicle routing programming problem. It involves
solution – with a novel ‘divide- problem (MVRP). Solutions for the minimising the total route cost and
and-conquer’ strategy inspired MVRP must factor in a fleet of vehicles establishing the maximum number
by dynamic programming. delivering to a myriad of customers of stops each vehicle can make while
while also considering traveling-time keeping operating costs to a minimum.
delays arising from traffic congestion. All It considers factors such as the number
this must be achieved at the lowest cost. of vehicles, vehicle capacity, time
Fortunately, three researchers – Jiaqi constraints, location of customers, order
Li, a graduate student at The University priority, speed limits, and traffic patterns.
of Hong Kong, and colleagues Yun
Wang from Zhejiang Sci-Tech University, The VRP is traditionally solved using
China, and Professor Ke-Lin Du from metaheuristics – strategies to guide
Concordia University, Montreal, Canada the search process to find optimal or
– have defeated the conundrum with near-optimal solutions – in the form of
an innovative mathematical solution an evolutionary or genetic algorithm
inspired by dynamic programming. (GA). GAs mimic biological evolution
????/Shutterstock.com

researchoutreach.org
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 Ensuring timely distribution and reducing the

cost of logistics is crucial to the viability of
ROUTING PROBLEM distribution and transportation businesses.
The MVRP extends the VRP to include
mixed-fleet vehicles with time windows
(specific time slots when visits must of vehicles; only one vehicle can arrive the next generation – or population.
be made). Fleets can consist of any or depart from a demand node; and, Elitist selection retains the individuals
combination of vehicles using traditional finally, there are no loops or duplicated with the best fitness values for the next
fuel, electric vehicles, and plug-in hybrids. sections within the optimised path or generation. Selected individuals form
The goal of the MVRP is to discover a set distribution sequence. a new population, and the process is
of routes that multiple vehicles can use to repeated for all paths between nodes for
serve numerous customers, which keeps DIVIDE-AND-CONQUER STRATEGY a vehicle’s complete route. This process
total costs to a minimum but still takes When creating their new divide-and- is repeated to find optimal distribution
traffic delays into account. conquer strategy, the researchers were paths for each of the remaining vehicles.
inspired by dynamic programming, where
Now researchers have developed a an optimisation problem is broken down REAL-LIFE APPLICATION
new mathematical model to solve into simpler sub-problems. When there The researchers verify the rationality
the MVRP using an improved genetic are a lot of demand nodes and road and feasibility of their model with
algorithm with a novel ‘divide- intersections, the problem is NP-hard, and a simulation using data from a
and-conquer’ strategy. Inspired by it isn’t easy to uncover an optimal route. manufacturer in Hangzhou, China.
dynamic programming, Li, Wang, Instead, Li and colleagues break the The manufacturer delivers products
and Du propose an distribution path problem into smaller sub-problems that to 40 customers. Analysing the results
optimisation method with two stages: they solve recursively. Initially, they find revealed that the new, improved genetic
a distribution sequence search and a

Researchers have developed a new

distribution path search.

VANQUISHING THE MVRP

The objective of the researchers’
mathematical model to solve the MVRP
proposed model is to find the shortest using an improved genetic algorithm with
possible route requiring the least
number of vehicles while keeping costs a novel ‘divide-and-conquer’ strategy.
to a minimum. Multiple vehicles are
being used to distribute products to an optimal sequence of demand nodes. algorithm – employing the divide-and-
multiple demand nodes, so the optimal Then, using their improved genetic conquer approach – converged on
number of vehicles required and the algorithm, they search for an optimal the optimal solution quicker than the
route for each vehicle will have to route between any two of the nodes and traditional, simple genetic algorithm.
be determined. build the complete route step by step. Moreover, the improved genetic
algorithm outperformed the traditional
This is modelled with two objective AN IMPROVED genetic algorithm for route feasibility,
functions (mathematical expressions GENETIC ALGORITHM route topology, and total cost.
whose values must be either maximised Each solution in a genetic algorithm
or minimised according to constraints). is referred to as an ‘individual’ and The researchers’ new methodology
The first objective function involves coded like a chromosome. A group of for solving the MVRP can help to
minimising the total cost. The second individuals form a ‘population’. Here, reduce the overall cost of a fast and
objective function minimises the total an individual is a route between two convenient distribution service. In
length of the route. These are subject nodes. Individuals are selected from addition to increasing logistics efficiency
to the following constraints: a vehicle’s the population using a combination of for manufacturers, distributors, and
maximum load capacity cannot be roulette wheel selection and an elitist transport companies, Li and his
exceeded; only one vehicle can fulfil a strategy. A roulette wheel is constructed colleagues’ model can be useful for
delivery at any node; all distribution jobs based on each individual’s relative other applications, such as optimising
are completed by the assigned number ‘fitness’ to select the individuals for manufacturing flow–shop scheduling.

researchoutreach.org
 The public outreach magazine for the research community

researchoutreach.org
Partnership enquiries: simon@researchoutreach.org

View publication stats