/udemy-tsp-and-vrp

Udemy course with solutions for Travelling Salesmen Problem (TSP) and Vehicle Routing Problem (VRP)

Primary LanguagePython

Learn optimization through Simulated Annealing and Tabu Search and solve the TSP and VRP problems with constraints!

https://www.udemy.com/course/optimizing-travelling-salesman-and-vehicle-routing-problems/learn/lecture/9917416?start=75#overview

Metaheuristics

Heuristics: a technique, which seeks optimal or near-optimal solution at a reasonable cost

Metaheuristics: heuristics that are inspired by nature and not proble-specific

See overview.png

Travelling Salesmen Problem - TSP

Problem

  • Visit all cities once and return to the same city
  • Determine optimal route
  • Symmetrical vs non-symmetrical
  • See TSP.png figure

Solution

Use 'Simulated annealing', see code

Eigen bevindingen

  • Lastig te volgen algoritme, see code
  • About 22 seconds for 7 nodes.

Vehicle Routing Problem - VRP

  • NP
  • combinatorial and integer problem
  • Variations like:
    • Capacitated Vehicle Routing Problem (CVRP)
    • Vehicle Routing Problem with Time Windows (VRPTW)

Problem

  • 5 trucks, 1 warehouse, 31 customers
  • minimize distance travelled
  • Constraints: 5 routes and truck capacity = 100

see screenshots

Solution

  • Use Tabu Search algorithm, see code
  • About 100 minutes to get solution, see log.