Project Topics
Get Complete Project Material File(s) Now! »
Different Kinds of Vehicle Routing Problems
There are several different types of vehicle routing problems (VRPs), and they have been studied extensively. The standard VRP consists of a number of vehi-cles and locations together with a number of driving assignments. The rules are set that each location has to be visited exactly once by a single vehicle, and the vehicle starts and finishes at a depot.
On top of the standard version, there are a lot of different types. They range from problems including Time Windows (VRPTW) 1, to problems dealing with Capacity constraints (CVRP) 2, and those where goods can be Simultaneously Picked up and Delivered (VRPSPD) 3 (the depot is not used as goods central any more). There are many more as well, including several combinations of the above mentioned types.
What Has Been Studied Before
The area of solving different variants of VRP is a field which has been studied intensively. Since the problem has been shown [20] to be NP-complete 4, the use of heuristics and approximate solutions plays a big part in finding solutions.
Different search algorithms have been used, among the most common ones are probabilistic algorithms, simulated annealing, local search methods or, a combi-nation of different methods (hybrid) 5.
Branch and Bound
One of the historically first papers to deal with VRPSPD is [13], which studies the distribution of books from a library in USA. The solving method was to first clus-ter the assignments according to geographical proximity, then to split the prob-lem into two parts. The first part became a Travelling Salesman Problem (TSP) and the second part dealt with satisfying the constraints derived from the loading coupled to the capacity constraints. The complete solution was then derived by solving the TSP, and then checking if the solution satisfied the constraints in part two. If the solution found for the TSP did not satisfy the constraints, a penalty was given to the route and then another iteration of TSP was performed.
Ant Colony Optimization
Another method to solve VRP’s is by applying a probabilistic method like for example Ant Colonization Optimization (ACO). In [14], a couple of different real-life VRP’s with time windows, VRPTW’s, are solved using ants and pheromones. The basic idea is to send out ants in the search graph and use heuristics, called pheromones, to make them choose the best route. Each ant represents a solution to either the full problem or to a section of it. The heuristics are based on both a priori and posteriori knowledge, and indicate the probability that an ant will choose a specific route. The probability depends on both the estimated desirabil-ity to choose that route, and the number of ants that have chosen that specific route previously.
Genetic Algorithms
In [18], the possibility to use genetic algorithms is displayed. A genetic algorithm works by finding a solution, and then trying to improve that solution by either breeding or mutating. Breeding means that two solutions, the parents, are com-bined to make a third one, the child. The child consists of parts from its parents, chosen by a routine. Mutating means that a solution is partially randomly trans-formed, creating an offspring with some new features. After either one, or both, the new solutions are evaluated and by some selection routine and probability, new parents are chosen.
Hybrid
A combined approach was used in [2], where Simulated Annealing (SA) and Large Neighbourhood Search (LNS) are combined into a hybrid solver. This al-gorithm works by first using SA to decrease the number of routes, and then LNS to decrease the total travel cost. SA works by permuting a solution into another one, and accepting the new solution as the current one if certain conditions are fulfilled. The new solution is accepted as the current if it:
• is better than the previous best.
• is worse than the previous best, but the randomly generated variable p is greater than a parameter that decreases with the temperature.
• together with all other new solutions is worse than the previous best, and none have satisfied the condition above, one solution is randomly chosen.
The parameter that decides whether or not a worse solution is accepted is the key for SA. It is often described as e t , where t is the temperature and is chosen to either make it easy or hard for worse solutions to pass. The temperature de-creases for each iteration SA performs, thus inferior solutions will have less and less probability to be accepted as the number of iterations increases. The best solution is stored and after a maximum time limit is reached, it is returned.
To reduce the total travel cost LNS was used. Bent and van Hentenryck de-scribes the use with ’The main idea behind LNS is to iteratively remove subsets of cus-tomers (gradually increasing the number of customers to remove at a time) from the best known solution and explore their feasible reinser-tion points in a systematic fashion’ [2, p. 881].
Financial Aspects
The financial aspects were considered in the beginning of this project, and though they are not covered in this thesis, they raise questions about the solutions of the problem of sharing the profits within the collaboration. Moreover, in [3] the order when approaching customers was discussed, together with mentioning the Shap-ley value. Different methods to share the profit have been studied extensively, for example in [1], [6], and [19].
The Vehicle Routing Problem in this Project
The problem in this thesis is a classical vehicle routing problem, combined with a couple of constraints that make it hard to solve. The main goal is to perform a number of driving assignments, delivering a number of parcels, from a set of customers to another set of customers. This means that the parcels are picked up during driving assignments and then carried by an HDV to a given location.
Problem Description
The driving assignments are also specified by time windows that set the earliest possible pick-up time as well as the latest possible delivery time. At the end of the day, the HDV should return back to its origin.
What makes this an interesting, and even more difficult, problem is that an HDV could perform assignments simultaneously, or instead of returning empty it could perform an assignment that has its delivery location close to where the HDVs origin is — thus decreasing the total cost. Another way to further decrease the cost — and consequently make the entire fleet more effective, is to use fewer HDVs and optimize the routing.
A difference to many of the problems studied, is that a parcel is specified to go between two pre-defined locations, thus it is not considered as an interchange-able material (for example sand) that could be thought of simply by its weight or volume. This makes the problem studied in this thesis to be a combination of CVRP, VRPTW, and VRPSPD.
The problem might not be solved using one of the algorithms found in the literary study, due to the complex constraints — especially the possibility of per-forming multiple driving assignments at once. With some modification it could be possible, but this has not been further studied in this thesis.
Restrictions and Interpretation
To make the problem solvable within the time given, certain restrictions are nec-essary. It is also necessary to state how the problem was interpreted, which leads to the solution design.
To begin with, the planning problem is assumed to be of a size and complex-ity that makes an analytical optimization intractable. This means that a search method of some kind is needed, and that the global optima might not be possible to find.
The restrictions are constructed to simplify the problem, and start with the fact that drivers are not considered. This means that driving constraints such as laws about resting, licenses for different HDVs etc. are neglected. Moreover, all HDVs are considered to be of the same type and size, which in turn also leads to the simplification that any assignment is considered possible to perform with any HDV. Again, this simplifies the problem and reduces the amount of different objects. Although assignments are simplified to be stackable with all other assign-ments, they have individual time windows and weights.
Versions of PDDL
There are many different versions of PDDL, where each version builds upon the last and specifies new requirements that should be supported. The new versions are often specified before one of the IPC competitions is held, and they are up-dated to increase the flexibility and functionality of the PDDL language. More-over, this means that planners competing in the IPC have to adapt to new condi-tions and functionalities.
The language of PDDL started with version 1.2 which was created in 1998 in order to make IPC-1 possible. PDDL 1.2 [12], states the basics of the language, such as how the domain and problem file should be composed.
One of the most important PDDL versions is 2.1 [5], which specifies the possi-bility to use numerical variables, plan-metrics, and durative actions which make planning with conditions such as fuel consumption, time constraints and capac-ity constraints possible. This master thesis also uses the specifications used in PDDL version 2.2[4], which contains specification for derived predicates and timed initial literals.
LPG-td
The planner chosen in this project is called LPG-td, and is designed by Gerevini, Saetti, Serina and Toninelli 3. LPG stands for Local search for Planning Graphs, and the LPG-td is a newer version of the old LPG. The new version adds addi-tional support for handling constraints relating to time. It was chosen mainly because it supports PDDL 2.2, but also because it produces competitive results and consequently won the planning competition in IPC3 (2002) and was awarded multiple awards in IPC4 (2004) 4.
LPG-td planner uses enforced hill climbing together with a best-first search to find feasible solutions. As a consequence of this search method, it is not guar-anteed that the planner finds the global optimum. The planner deals with this by offering the possibility to execute with three commands; speed, quality or n hintegeri. Together with a maximum time limit, they will return different solu-tions accordingly:
• speed will find one solution and present it.
• quality will spend an automatically decided time on improving the first so-lution.
• n hxi will find x solutions (if the time limit is not reached before), where the objective function values of the x solutions follows valj vali if j > i: (3.1).
Table of contents :
1 Introduction
1.1 Background
1.2 Long-term Goals
1.3 Project Goals
1.4 Outline
2 Problem Description
2.1 Different Kinds of Vehicle Routing Problems
2.2 What Has Been Studied Before
2.2.1 Branch and Bound
2.2.2 Ant Colony Optimization
2.2.3 Genetic Algorithms
2.2.4 Hybrid
2.2.5 Financial Aspects
2.3 The Vehicle Routing Problem in this Project
2.4 Restrictions and Interpretation
2.5 Constraints
2.6 Objective Function
3 Search-Based Problem Solving
3.1 Search Algorithms
3.2 PDDL
3.3 Versions of PDDL
3.4 LPG-td
3.4.1 PDDL Features
3.4.2 Planning
3.4.3 LPG-td Accomplishments
4 Implementation
4.1 Domain File
4.1.1 Types
4.1.2 Predicates
4.1.3 Functions
4.1.4 Actions
4.2 Problem File
5 Evaluation
5.1 Definitions
5.2 Different Planners
5.3 LPG-td Scaling
5.4 LPG-td Performance
5.5 LPG-td Relative Improvement
5.6 Case Study Problem
6 Conclusions
7 Discussion
7.1 Transport and Solving Problems
7.1.1 Choice of Planner
7.1.2 Understanding How the Planner Works Versus Usability .
7.1.3 Heuristics
7.1.4 Soft Constraints
7.1.5 Adaptivity of PDDL
7.2 Financial Aspects
7.2.1 Is There Anyone Interested in a Service Like This?
7.2.2 Sharing Profits and Resources Between Participants
7.2.3 How to Approach Companies in Best Fashion
7.2.4 Assumption of No Rivalry Among Participants
7.2.5 Financial Regulations and Laws Against Collaborations
8 Acknowledgements
Bibliography
