Learn optimization through Simulated Annealing and Tabu Search and solve the TSP and VRP problems with constraints!
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.