Tour planning

from Wikipedia, the free encyclopedia

Tour planning is a planning process in which (transport) orders are grouped into tours and put in a sequence. A tour is usually carried out by one person or a vehicle. This planning process is important in all areas in which a large number of orders and tours have to be planned. Examples are the delivery to branches of a retailer, the collection of mail, the garbage collection, the transport of people and the use of service personnel. At regular distances as in the courier express package service form so transport network structures .

An order usually consists of bringing a certain number of units of a shipment from a start to a destination. A solution to a route planning problem therefore usually has two aspects:

  • the clustering indicates which orders are grouped into a tour
  • the routing defines the order in which the points are served within a tour.

The objective of route planning is, for example, to minimize the number of vehicles used, the distance covered, the operating time, CO 2 emissions or a more complex cost function. In the standard route planning problem , all start or destination points are located in a depot and a limited or unlimited number of identical vehicles with limited capacity are available there. Other variants consider additional restrictions such as B. time windows, several depots or any starting and destination points (so-called pickup and delivery problems ).

In reality, the task is expanded by many restrictions. For example, one looks at several depots, a heterogeneous vehicle fleet or priority relationships between orders. Another possible additional task is the consideration of time windows within which a vehicle has to arrive at the customer in order to comply with the slots allocated or booked by a time window management . Dynamic route planning is used when the order situation changes dynamically during planning (for example, due to new or canceled orders).

In addition to the logistics sector, applications exist in all branches of the economy that supply their customers (for example, the furniture industry, garbage disposal or vending machines). In many companies, route planning software is used to compile the resulting routes and to optimize them based on criteria such as adherence to time limits or weight limits, as well as transport costs.

Mathematical models and algorithms

The basic model of route planning belongs to the class of NP-difficult problems. Therefore, heuristics are used to solve the problem . The savings heuristics and the sweep algorithm are simple solution methods . Better quality solutions are based on evolutionary algorithms , simulated cooling and taboo searching . You use local search strategies in which the sequence of orders or assignment of orders to vehicles is swapped. Recently, the ant algorithm has also been increasingly considered as a problem solution.

As a sub- problem of tour planning, there is the problem of the traveling salesman , considering a vehicle with unlimited capacity and letting it drive with minimal cost or distance.

Def .: A set of orders is to be assigned to a set of means of transport, taking into account distances and restrictions, so that all total transport costs caused by the use of means of transport and the distances covered are minimized.

Tour planning software

Tour planning software supports companies in planning and optimizing tours. For this, the software needs u as a database. a. a digital road network, a customer master file, a vehicle and driver list and a current order list. Distances and travel times can be roughly estimated with the help of coordinates of the geo- referenced customer addresses or taken from a distance set ; alternatively, algorithms for route optimization operate on a digital road network. The optimization is done by combining the transport needs of a number of customers into one or more tours in such a way that the customer's time requirements, loads and capacities of the vehicles, breaks and working times of the drivers and maintenance cycles of the vehicles are adhered to while the transport costs incurred are minimized . These may consist of fixed costs for the driver, dispatcher and vehicle as well as the variable fleet costs consisting of consumption costs, toll costs, maintenance and repair, working hours and overtime.

See also

literature

  • Wolfgang Domschke and Armin Scholl: Logistics: Round trips and tours. 5th edition, Oldenbourg-Verlag, Munich, Vienna 2010. ISBN 978-3486590937 .
  • Tore Grünert and Stefan Irnich: Optimization in Transport, Volume I: Basics. Shaker Verlag , Aachen 2005. ISBN 978-3832245146 .
  • Tore Grünert and Stefan Irnich: Optimization in Transport, Volume II: Routes and tours. Shaker Verlag, Aachen 2005. ISBN 978-3832245153 .
  • Heinrich Paessens and Philip Herbst: Tour planning with TourMaster 4. expertSoft 82, Expert Verlag, Renningen 2010. ISBN 978-3816929185 .

Web links

jsprit - Open Source Java Library for solving complex route planning problems