Vehicle routing problem
Under tour one understands the problem, the best possible allocation of vehicles to jobs and to find an optimal order of to-use job sites for each vehicle when it logisticians, logistics service providers and freight forwarders. A job consists mostly is to bring a certain number of units of a consignment from a start to a destination. A solution of a tour planning problem usually has therefore two aspects: the clustering indicates which jobs are grouped together for a tour, and the routing defines the order in which the points are served within a tour. Objective of a tour, for example, minimizing the number of vehicles used, the distance traveled, the use of time, CO2 emissions or a more complex cost function. In the standard problem of the tour are all starting or destination points in a depot and now there are a limited or unlimited number of vehicles available. Other variants consider additional capacity restrictions for the vehicles ( Capacited vehicle routing problem, CVRP ), multiple depots, or any start and end points (so-called pickup -and -delivery problems).
In reality, the task is further enhanced by many restrictions. For example, one considers several depots, a heterogeneous fleet of vehicles or precedence relations between jobs. Another possible additional task is the consideration of time windows within which a vehicle must arrive at the customer to comply with the management of a time window allocated or booked slots. From a dynamic tour is called when the order situation during the planning changed dynamically (for example, through the newly added or canceled orders ).
Applications exist in addition to the logistics sector in all economic sectors, which supply their customers (for example, furniture industry, refuse collection and automatic feeder ). In many companies, trip planning software is used to compile the resulting tours and optimize based on criteria such as compliance with deadlines or weight limits, as well as transportation costs.
Mathematical Models and Algorithms
The basic model of the tour belongs to the class of NP-hard problems. Therefore heuristics are applied to solve the problem. Simple solution procedures are the Savings heuristic and the sweep algorithm. Solutions with better quality based on evolutionary algorithms, simulated cooling and tabu search. They use local search strategies, in which the sequence of orders or assignment of contracts is traded to the vehicles. Lately, the ant algorithm is also more and more often considered as a problem solving into account.
As a subproblem of the tour there is the problem of a Salesman, by looking at a vehicle with unlimited capacity and this can drive with minimal cost or path length.
Def: A set of orders is a lot of means of transport, taking into account distances and assign restrictions so that all total transport costs, which are caused by the use of means of transport and the distances traveled are minimized.
Route planning software
Trip planning software helps companies plan and optimize routes.
This requires the software as a data base, among other things, a digital road network, a customer master file, a vehicle and driver as well as a list of current job list.
Distances and travel times can be roughly estimated using the geo-referenced coordinates of customer addresses or removed from a Distance Matrix, alternatively operate algorithms for route optimization on a digital road network.
The optimization is done by the transport needs of a number of customers will be combined into one or more tours in such a way that temporal requirements of the customers, loads and capacities of the vehicles, breaks and working hours of drivers and maintenance cycles of the vehicles are kept, while the transport costs are minimized.
This may consist of fixed costs for drivers, dispatchers and vehicle as well as the variable fleet costs consisting of consumption costs, toll costs, maintenance and repair, and overtime hours.