The basic purpose of the PTV xTour Server is to solve the vehicle routing problem (VRP) seeking to serve a number of customers with a fleet of vehicles. Thereby several planning objects are involved.
Depots (required input data)
A depot is a site where vehicles are located before they perform tours. The required delivery quantities are stored at the depot. The pickup quantities have to be brought to the depot. Thus depots act as supply depot, storage depot and vehicle fleet as well.
Vehicle fleet (required input data)
A fleet represents the necessary resources to perform the tours. It consists of vehicles and trailers as well as of rules for the combination of vehicles and trailers (so-called trains). The vehicles and trailers are usually located at a depot. They may perform several tours in a so called tour chain.
Transport orders (required input data)
A transport order is the basic planning object which has to be performed once. There are two types available:
The depot transport order represents the transportation of goods between a depot and a transport point. The transport point is usually related to a customer address. It is possible to model delivery and pickup of goods.
The AB transport order represents the transportation of goods between two transport points. That means that in this case the goods are not supplied or stored in a depot.
Tours (optional input data)
A tour is usually depot-related, that means a vehicle starts at a depot, then serves transport orders and finally returns to a depot (more possible tour structures are described later). The tours are the main result of the planning. In the case of a green field approach no tours need to be imported. But if you want to optimise existing tours, they have to be imported like the other planning objects.
For the VRP there are two problems to be solved: Which transport orders are assigned to which vehicle tours? How is the sequence of the transport points within the vehicle tours? The build in planning algorithms try to solve this problem considering several optimization goals:
The best solution would be one tour containing all transport orders, but usually the given capacity or time restrictions demand more than one tour.
The PTV xTour Server is able to solve a multi depot vehicle routing problem (MDVRP). So it is not necessary that every transport order is assigned to a dedicated depot in advance. The tour planning algorithm is able to assign the transport orders to depots and plan the tours in one step.
Depending on the chosen tour planning step and method there are different modes used:
The classical VRP deals with round tours. Besides the planning of round tours more tour structures are possible:
Round tour
The tour starts at a depot, then serves some transport points and finally returns to the same depot the tour started.
Open tour
Similar to the round tour the open tour starts at a depot, then serves some transport points and finally returns to a different depot the tour started.
Start-depot-free tour
The tour starts at the first transport point to be served and ends at a depot. A reason for a missing start depot could be the billing method (e.g. the tour from the start depot to the first transport point is not paid).
End-depot-free tour
The tour starts at a depot and ends at the last transport point to be served. A reason for a missing end depot could be the billing method (e.g. the tour from the last transport point to the end depot is not paid).
Depot-free tour
The tour starts at the first transport point to be served and ends at the last transport point to be served.
Please note that only in the case of round tours it is possible to perform several tours one after another with the same vehicle (a so called tour chain). For all other tour structures no more than one tour per vehicle is valid. Moreover you have to specify on client side which vehicle is located at which depot or more precisely which is the valid start depot (or none) and end depot (or none) for every single vehicle. So the possible tour structure for a vehicle is not determined by the tour planning algorithm.
The VRP is an NP-hard (Non-deterministic Polynomial-time hard) problem, so this class of problems could not be solved in polynomial time. This means that the machine time required to solve even moderately sized problems can easily exceed all acceptable levels of efficiency. For that reason often heuristic or approximation algorithms are used to solve the VRP, especially for practise-oriented problem sizes. They can find in an acceptable machine time a good solution. This solution is not a guaranteed optimal solution as if using exact algorithms, but it is often nearby with regard to the solution quality. Hence in the PTV xTour Server are in large parts heuristics used.
The heuristic algorithms could be classified in construction and improvement methods. The construction method tries to find a first valid solution keeping all restrictions. The improvement method starts with a valid solution (e.g. as result of a construction method) and tries to improve this solution by modifying small parts of it. The main planning steps of the PTV xTour Server are structured in the same way:
Construction step
This step tries to build new tours and to complete existing tours in the case of imported ones. Usually the integrated heuristic provides a rather good result in a short machine time.
Improvement step
This step tries to change transport orders between the planned tours. Usually the integrated heuristic is used to improve the result of the construction step, but depending on the problem this may take some machine time.
During the tour planning the PTV xTour Server is able to consider a lot of restrictions. The most important ones are explained below:
Opening intervals
Spans one or several time windows at the depot and transport points in which all activities must be carried out (e.g. up- and unloading).
Operating intervals
Spans one or several time windows at the vehicle in which the vehicle can operate. Beyond these operating intervals the vehicle must not be moved and the dedicated driver is not allowed to work.
Capacity patterns
Loading capacity pattern of the vehicle for maximum 10 different kinds of goods (e.g. compartments with a predefined good assignment) or different units of measurements (e.g. weight, volume, turnover). As the quantities of the transport orders have to be defined in the same way, every capacity in the pattern vector must not fall below the corresponding quantity on the vehicle tour at each point in time. Moreover there is more than one capacity pattern per vehicle definable to model flexible loading areas. At least one capacity pattern has to be valid during the whole tour (e.g. transportation of 5 non-handicapped students or after moving the seats 2 non-handicapped and one handicapped student).
Tour restrictions
Maximum values constraining the resulting vehicle tours (e.g. the maximum number of transport points in a tour or the maximum driving period or distance of a tour).
Break- and rest rules
Complete driver rules of the European Union (REGULATION (EC) No 561/2006). As there are lots of valid solutions (permanent decision between keep on driving or having a break), the build-in algorithm tries to find the earliest possible arrival time at the end of the tour and thereby to delay the tour start as far as possible to avoid unnecessary waiting periods. Moreover it is possible to consider the German working hours act. Both the EU and the German regulation are modelled as a set of adaptable rules for future changes or for other countries to a certain extend.
Copyright © 2024 PTV Logistics GmbH All rights reserved. | Imprint
