 |
 |
Vehicle Routing Problems (introduction)
|  |
Routing in its most basic form is a question of getting from A to B as fast as possible.
Sometimes you want to go from A to B via C or you have to adhere to various restrictions (one-way, max-weight, etc.).
But basically it is still the same shortest path problem.
When you want to visit several customers after each other and want to minimize the total length of the trip, it is a
very different kind of problem: The well-known Travelling Salesman Problem (TSP). The TSP is supported by RW Net/NetServer
and RouteFinder.
More complex problems:
VRP / VRPTW
If you have more customers to visit than can be covered on a single trip, we call it the vehicle routing problem or VRP.
If further more time windows are added, so some customers has to be visited at specific times of the day, we refer to it as the Vehicle Routing Problem with Time Windows or VRPTW.
The list below show some of the possible real-life restrictions:
• Service time spent at each customer
• Different start/end position for a customer (when the task is to drive from one place to another)
• Capacities on vehicles
• Maximum length of trips
• Round-trip / out-bound / in-bound
• Priorities for different customers (i.e. visit only a subset of the customers, if too little time)
• Multiple time windows per customer (i.e. visit between 8 and 9 or between 10 and 11)
• Separate costs for driving time, waiting time, driving distance and number of vehicles
• Main time window
• Customers can only be served by a subset of the available vehicles
• Multiple depots (i.e. where the serving depot is determined by the algorithm)
• Different vehicle types
• Drive-time between locations depending on the time of day
• Different start / end locations for routes (they all start at the single depot).
• Maximum no of vehicles
• Multi-day planning
• Mixed pickup & delivery on the same route (only relevant to distinguish if weight/volume capacity is implemented)
See FleetEngine for such functionality.
|
|
|
|
