Ye Yuan
0%

Vehicle Routing Problem

Posted on Edited on

Vehicle Routing Problem

VRP

The classical vehicle routing problem (VRP) aims to find a set of routes at a minimal cost (finding the shortest path, minimizing the number of vehicles, etc) beginning and ending the route at the depot, so that the known demand of all nodes are fulfilled. The VRP belongs to the class of NP-hard combinatorial problems.

The problem is to find a set of least-cost vehicle routes such that:

  • each vertex in is served exactly once by exactly one vehicle;
  • each vehicle route starts and ends at the depot;
  • all side constraints are satisfied (capacity, maximum travel distance or maximum travel time).

Multi-Depots VRP

The MDVRP can be defined by a graph , where is the vertex set and the edge set. The vertex is partitioned into two subsets and representing, respectively, the set of places to visit and the set of depots. At each depot, a maximum of vehicles of capacity are available. Each vetex has a nonnegative demand and a nonnegative service duration . A distance matrix is associated to set . In a MDVRP, one wants to define at minimum cost the set of vehicle routes such that:

  • each route starts and ends at the same depot,
  • each customer is visited exactly once by a single vehicle,
  • route demand cannot exceed the vehicle capacity,
  • route duration (including travel and service times) does not exceed a preset limit.

Formulations of VRP and MDVRP

skip

Methods Summary

There are numorous methods have been applied into MDVRP,

  • Exact Methods
    • Branch and Bound
    • Interger Programming
  • Heuristic Methods
  • Meta-Heuristic Methods
  • Reinforcement Learning

Heuristic v.s. Meta-Heuristic [3]: - Heuristics: problem dependent techniques that are usually adapted to the problem at hand; - Meta-heuristics: problem independent techniques that can be used as black boxes and can be applied to solve a wide range of problems.

Routing Considering Arrival Probability

where is the travel time budget between origin and destination . Each edge has an independent random variable trave time .

References

[1] @article{karakativc2015survey, title={A survey of genetic algorithms for solving multi depot vehicle routing problem}, author={Karakati{}, Sa{}o and Podgorelec, Vili}, journal={Applied Soft Computing}, volume={27}, pages={519--532}, year={2015}, publisher={Elsevier} }

[2]

[3] https://www.researchgate.net/post/What_is_the_exact_difference_between_heuristic_and_meta-heuristic_algorithms