There’s the Traveling Salesman Problem (TSP). Then there’s the Job Shop Scheduling Problem (JSP). Then there’s the Vehicle Routing Problem (VRP). Then there’s the Vehicle Routing Problem with Pickup and Delivery (VRPPD). Then there’s the Vehicle Routing Problem with Time Windows (VRPTW). Then there’s the Capacitated Vehicle Routing Problem (CVRP).
Then there’s your real-world problem: Capacitated Vehicle Routing with Time Windows, Pickup and Delivery, Customer Preferences, Problem Cases, Job Shop Scheduling, Service Priorities, Service Dependencies, Legacy Systems, and Non-normalized Data.
Oh, also what’s getting “delivered” are actually human beings, in this case drivers who actually need to pick up other vehicles and drop them off at service locations. So additional constraints will include bio breaks (e.g. lunch hours by time zone) and safety considerations (e.g. over-optimization can lead to dangerous driving behavior, or even risk of heat stroke in peak summer).
Gotta take care of your people. They are what matters.
So yeah… math is easy. It’s reality that is hard.
Good luck 👍
And management might object 😜
The travelling salesman problem (TSP) asks the following question: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?” It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.
The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks “What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?”. It generalises the well-known travelling salesman problem (TSP). It first appeared in a paper by George Dantzig and John Ramser in 1959, in which first algorithmic approach was written and was applied to petrol deliveries. Often, the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. The objective of the VRP is to minimize the total route cost. In 1964, Clarke and Wright improved on Dantzig and Ramser’s approach using an effective greedy approach called the savings algorithm.
Determining the optimal solution to VRP is NP-hard, so the size of problems that can be solved, optimally, using mathematical programming or combinatorial optimization may be limited. Therefore, commercial solvers tend to use heuristics due to the size and frequency of real world VRPs they need to solve. (For a non-technical explanation of why the VRP is so challenging please see the External Links below.)
The VRP has many obvious applications in industry. In fact, the use of computer optimization programs can give savings of 5% to a company as transportation is usually a significant component of the cost of a product (10%) – indeed, the transportation sector makes up 10% of the EU’s GDP. Consequently, any savings created by the VRP, even less than 5%, are significant.
Due to the difficulty of solving to optimality large-scale instances of vehicle routing problems, a significant research effort has been dedicated to metaheuristics such as Genetic algorithms, Tabu search, and Simulated annealing. Some of the most recent and efficient metaheuristics for vehicle routing problems reach solutions within 0.5% or 1% of the optimum for problem instances counting hundreds or thousands of delivery points. These methods are also more robust in the sense that they can be more easily adapted to deal with a variety of side constraints. As such, the application of metaheuristic techniques is often privileged for large-scale applications with complicating constraints and decision sets.