Route optimization is probably the most famous application of operations
research and perhaps its value in this context is easiest to understand.
The goal is
to find paths for vehicles that collectively must visit a set of
customers. In the age of e-commerce, this problem is being solved
daily by courier companies like FedEx, DHL and Amazon. Good solutions
bring forth time, fuel and CO2 savings which all mean lowers costs.
The problem is notoriously difficult to solve to optimality. So usually simpler and faster algorithms are used in practice. The exact choice of solution method depends on your needs - the problem sizes you are facing (how many customers) and an acceptable waiting time for the algorithm to finish (how many seconds or minutes).
As it is a very popular application, it has a large number of variants. In the demo below, we are solving just 4 types of vehicle routing problems. The first one is a classical travelling salesman problem where a single salesman (vehicle) must visit all customers. The second example includes 4 vehicles with the goal of equalizing the driving distance for each driver, a common objective in many applications to ensure a "fair" load on workers. The third option includes time windows, meaning that a customer can only be visited during certain hours of the day (for example before or after working hours). Finally, the fourth example considers delivery and vehicle capacities, so the shortest routing might not be possible due to all the cargo not fitting in a vehicle.
Click to run an example and the optimal paths with respect to the constraints will be shown on the map below.
© OpenStreetMap contributors