Development of a New Delivery Optimization Method Using an Annealing Machine

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)

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.