Vehicle Routing Problem

Question 1

VRP is highly relevant in practice: name examples

Answer 1

→ short-haul transportation (vehicles, transportation requests)
→ machine scheduling (machines, production requests)
→ warehousing / order picking (pickers, customer orders)

Question 2

Name the challenge of VRP

Answer 2

computationally challenging (theoretically and practically)
optimization problems
→ many exact methods used/perfected for VRPs rst
(branch-and-cut, column generation/branch-and-price)

Question 3

Task of Capacitated VRP

Answer 3

• Find distance/cost-minimum set of vehicle routes for a
  homogeneous vehicle eet, such that
  –> each vehicle route starts and ends at the depot
  –> each customer is served exactly once
  –> the total demand transported on each route does not exceed
  the vehicle capacity

Question 4

Fundamentals of CVRP

Answer 4

• Capacitated vehicle routing problem (CVRP) as fundamental
  problem in route planning
• Identical vehicles with known capacity located at depot
• Must deliver certain quantities of goods (stored at depot) to a set
  of customers
• Each customer must be visited exactly once
• Respect capacities of vehicles
• Common objectives: minimize traveled distance / cost, minimize
  number of vehicles

Question 5

Difficulty of CVRP compared to TSP

Answer 5

• Clustering problem renders CVRP more diffcult to solve than
  TSP from practical viewpoint. Both problems are N P -hard,
  but:

–> TSPs with several thousand cities can be solved to optimality
–> for CVRP, exact methods are in general limited to 200 to 250
customers → instance dependent; runtimes in the range of
many hours; methods extremely sophisticated and complex