Background/Problem Statement

The Vehicle Routing Problem (VRP) refers to the issue of finding feasible/optimal routes for a fleet of vehicles to minimize the number of vehicles utilized, and total distance and travelling time taken by all vehicles while satisfying all the given constraints. VRP is a well-known hard optimisation problem and is intractable in both theory and practice.

Furthermore, in practice, there are many types of VRP problems, which may correspond to different approaches to solve the problems.

It is, therefore, necessary to develop solvers which can handle a broad range of different VRP instances and give reasonable solutions in a reasonable time, and which can also fit within a VRP as a software service. Due to the intractability of VRP, solvers which give optimal solutions may not be feasible in practice, hence the emphasis on reasonable quality and efficiency.

Solution

1. Improved VRP solver: An improved VRP solver, based on local search, has been developed for a key VRP instance, and results show that the solver is more advanced due to more refined approaches to the objective function and more accurate distance matrices. Another VRP engine developed using Google OR-Tools as the base shows that the VRP engine can be relatively fast if a real-time vs solution quality tradeoff is desired. 
   
   
2. VRP solution verifier: The quality and assessment of VRP solutions depend very much on what is the chosen objective function and parameters used. A better objective function and parameter settings can significantly improve the VRP solution, for a particular VRP instance, leading to better performance and lower costs. An experimental VRP solution checker or verifier has been developed to check the validity of VRP solutions for various VRP problems.

Improved solution quality for studied VRP instances demonstrates that lower cost and more robust routing is feasible with solver improvements.

There is potential for a more powerful VRP engine to be developed for more complex VRP instances with different kinds of customization constraints that can, in principle, achieve increased power and flexibility.

Benefits

• Improved service quality 
• Lower costs
• Greater customer satisfaction 
• Improved vehicle utilization

Potential Application(s)

Logistics & transportation industries

We welcome interest from the industry for collaboration/ co-development / customisation of the technology into a new product or service. If you have any enquiries or are keen to collaborate, please contact us.