I try to solve VRP with genetic algorithm and then from literature; I found that we can simplify VRP by classifying vehicles. (First classify vehicles and run TSP algorithm for all class.)
How can I do this ? I can do this with machine learning but I wonder is there any algorithm for this. Or is it a general method for VRP ?
I did not get the classification point (First classify vehicles and run TSP algorithm for all class.) .. What does it mean?
Usually, VRP is a combinatorial optimization problem, in order to solve it you should design the solution representation for each chromosome in the population.
First, you should specify the no. of variables in the case study, for example: distance, time, cost... etc.. these are variables. Each variable has Lower and Upper bound. Then, the chromosome should consists of several genes - or variables - each one represents a random value in the range [Upper, Lower].
That was the general solution representation for the TSP, or VRP.
Hope this helps,
Regards..
Hello Barış,
The approach you suggest sounds related to "cluster-first route-second" heuristics for vehicle routing problems:
Article A Generalized Assignment Heuristic For Vehicle Routing
However, these "constructive" methods are very basic and generally do not produce solutions of good quality for the VRP. Indeed, the choices of clusters (i.e., customers-to-vehicles assignment choices) are tightly interrelated with the visit sequences (TSP) decisions, such that any method that optimizes sequentially these two decision sets makes a lot of approximations (since it is unaware of the true cost of each decision). Some of these aspects are discussed in the following papers:
Article Heuristics for Multi-Attribute Vehicle Routing Problems : A ...
Article Heuristics for vehicle routing problems: Sequence or set optimization?
Good luck !
This way
First classify vehicles and run TSP algorithm for all class
Is the most popular. However, there are other alternatives that considers cellular automata or others.
You may encode a solution as a single route (a solution for the TSP) to perform the operators of the genetic algorithm. Then, before evaluates a solution (the single route), you split that single route into a set of routes using the Basic Split procedure. This procedure returns the optimal split for a given sequence of nodes. You can a description of this method in the paper "Order-first split-second methods for vehicle routing problems: A review" from Christian Prins, Philippe Lacomme, and Caroline Prodhon, available at https://www.sciencedirect.com/science/article/pii/S0968090X14000230
My explanation is TSP is VRP with the condition that only 1 truck is in operation or only 1 salesman. In other word, the VRP solution can have many routes but TSP solution has only 1 route. TSP is the simplest problem of VRP.
In addition, in the year 1959, Dantzig and Ramser, the authos of "The truck dispatching problem" described how the Vehicle Routing Problem (VRP) may be considered as a generalization of the Travelling Salesman Problem (TSP). They described the generalization of the TSP with multiple salespeople (supposedly riding a single vehicle each), and called this the “Clover problem”. You can read more about the VRP and its many variants in "A Survey on the Vehicle Routing Problem and its Variants"
You have to classify the vehicles according to it number and based on the classes you have got, then you can run TSP code for each class.
- Badges
- Science topic