1
$\begingroup$

I would like to know how vehicle routing software optimizes routes? In demos of this software, they provide the optimal (or a good) route in just a few seconds or minutes with several nodes (maybe 50 or 100). What are the main algorithms used to solve this type of problem? Moreover, in software, it is possible to define the location of nodes by clicking on the map and it adds another step to determine the distance of nodes. However, the software can easily solve the problem.

$\endgroup$
  • 2
    $\begingroup$ Which software you are talking about? $\endgroup$ – Ruslan Sadykov Nov 2 '20 at 8:39
  • 1
    $\begingroup$ maybe start by seeing the code for open source projects such as OptaPlanner, OR-Tools, VROOM, ODL Studio, VRPSolver and VRPy $\endgroup$ – dhasson Nov 2 '20 at 12:42
  • 2
    $\begingroup$ This very much depends on the types of routing problems handled. In the absence of complicating factors (capacities, time windows, multiple vehicles, ...) the generation of a single route might just be an application of Dijkstra's shortest path algorithm. $\endgroup$ – prubin Nov 2 '20 at 19:49
  • $\begingroup$ The vast majority of route optimization software relies on local search approaches. Here is a paper describing such an approach for a real-life inventory routing problem encountered in the industrial and medical gas industry: localsolver.com/fgardi/downloads/… $\endgroup$ – LocalSolver Nov 3 '20 at 9:45