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$
4
  • 2
    $\begingroup$ Which software you are talking about? $\endgroup$ Commented Nov 2, 2020 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
    Commented Nov 2, 2020 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
    Commented Nov 2, 2020 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$
    – Hexaly
    Commented Nov 3, 2020 at 9:45

0