Theme
In recent years, while the demand for deliveries has increased, the rise in redeliveries and the shortage of
delivery personnel have become issues in local small-scale deliveries. Further cost reduction is difficult, so
we believe that it is necessary to realize the new added value of 'immediate delivery' through the
computational speed of annealing machines. In this 2023 MITOU Target Program, we worked on developing an
algorithm that quickly solves the multi-objective optimization problem, considering not only efficient route
exploration to minimize the travel distance of delivery personnel but also minimizing the waiting time for
consumers.
Details of the combinatorial optimization problems
This is a multi-objective optimization problem based on the Capacitated Vehicle Routing Problem (CVRP) that
considers minimizing consumer waiting time. Waiting time is measured at each consumer location, and the
delivery routes are proposed simultaneously for the number of delivery personnel to minimize the total waiting
time across all deliveries.
Decision variables
Two-dimensional decision variables, delivery personnel (i) x delivery location (j) (1 if going to the
delivery location, 0 if not)
Image of decision variables
|
Visiting Locations (j) |
Shop |
Order a |
Order b |
Order c |
・・・ |
Delivery Personnel (i) |
A |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
|
B |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
|
C |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
|
D |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
|
・ |
|
|
|
|
|
・ |
|
|
|
|
|
・ |
|
|
|
|
|
Objective function
- Minimize delivery distance
- Minimize variance in consumer waiting time distribution
Constraints
- Constraints on the weight that delivery personnel can carry
- Constraints to prevent passing the same location multiple times
Challenges
Since CVRP is a well-researched area, it was challenging to investigate existing methods and consider
differentiation. Through interviews with potential users and further investigation, we focused on the local
small-scale delivery sector, which has not yet been extensively optimized. We decided to develop an algorithm
that not only enhances efficiency and reduces costs but also provides the added value of "immediate delivery".
In program development, having inequality constraints about weights makes it challenging to find high-quality
solutions in a short calculation time as the problem scale increases. Therefore, considerable effort was
required in preprocessing and designing decision variables. Additionally, it was challenging to adjust the
weights between objective functions and the constraints in multi-objective optimization. We made step-by-step
improvements by getting hints from conversations with the project manager and other team members.
Future Outlook
In the future, we hope to turn this into a service, but with the current approach, there is a challenge in
obtaining high-quality solutions in a short calculation time as the problem size increases. We believe we
still need to consider problem simplification, preprocessing and designing decision variables, variable
reduction, problem decomposition, and other aspects. Additionally, to commercialize this, further
consideration of business aspects such as pricing and operational costs is necessary.
Achievements / Gratification
The applicability of quantum annealing is very significant, and it has been beneficial to understand through
the project that it is an effective method for solving NP-hard combinatorial optimization problems that were
extremely difficult to solve with traditional computers. Also, having once engaged with the combinatorial
optimization problem, we feel that our perspective has broadened, recognizing many things as combinatorial
optimization problems.
To Viewers
With the advancements in quantum computers (D-Wave) and GPU annealers, it has become possible to apply them
to practical problems. From the perspective of application development, it has become very exciting, so we
encourage everyone to give it a try!
* All information in this article is based on information available at the time of the interview.