In this blog we will be discussing how to solve a capacitated vehicle routing problem (CVRP) using genetic algorithm to minimize the time of delivery operation.
If you are not familiar with genetic algorithms, then I suggest you to check out this blog where I have described the workings of the algorithm in detail.
First, we will describe the optimization problem and then we will formulate a solution.
Problem Statement
This is a problem of delivery planning for the LPG (Liquified Petroleum Gas) distributor. The distribution company delivers LPG to the bulk customers by a fleet tanker lorry. There is a fleet of 25 tanker lorries operating from 5 depots in the fictional country of Optilandia.
The tank capacity and delivery costs are summarized in the table shown below.
The lorries distribution in the depots is shown in the table below.
Moreover, the speed of tank lorry is 50 miles/hour on average by considering safety, regardless of the lorry's capacity.
We are given:
Three csv files:
SaO_Optilandia_locations.csv containing the following columns:
id: Location ID
x, y: coordinates of a location
is_depot: True if a location is one of the five depots
is_customer: True if a location is one of the customers
capacity: capacity of the tank in tonnes ( only for customer locations)
level: current gas level in the tank in tonnes (only for customer location)
2. SaO_Optilandia_links.csv containing the following the:
id1, id2: Location IDs connected by a road segment.
3. SaO_Optilandia_depot_lorries.json file that contains information about the types and capacities of tanker lorries in each depot as given in Table1 and Table2.
Example of calculating dispatch time:
The loading time at depot can be omitted (not included as dispatch time), however, the travel time and offloading time will be included into the dispatch time. The offloading time consists of constant fixing time of 5 minutes at a customer, and 10 minutes per tonne for dropping the gas from tank to customer.
With above mentioned large tank with 10 tonnes of LPG travelling 20 miles to drop 2 tonnes to a customer, the dispatch time imposed is:
(20 [miles] / 50[miles/hours]) x 60 [ multiplying by 60 to change hours to minutes] + 2 [tonnes] * 10[minutes/tonne] + 5[minutes] = 49 minutes.
Objective:
To minimize the overall dispatch time (time taken by all the lorries to complete the delivery of LPG to all the customers by fully filling their tanks) keeping in mind the constraint of lorry capacities.
Now that we are familiar with the problem at hand we can proceed to find out the best possible solution.
Solution
We will first assign customers to each depot. One way to do this is to assign those customers to a depot who live nearby based on their Euclidean distance from the depot.
You can think of it as creating five clusters of customers with each depot as the center of the cluster.
The figure below shows the allocation of customers to depot with location id 523.
The green nodes in the above graph represents the no. of customers assigned to depot having location id 523.
The no. of customers assigned to each depot in this manner is as follows:
The lorries of each depot will only cater to the needs of the customers assigned to their depot. By doing this we ensure that the lorries won't be travelling far and hence it will help in reducing the dispatch time.
The next step is where Genetic Algorithm (GA) comes into play.
Chromosome encoding:
In order to work with GA we need to decide the encoding for the chromosome. For this problem the chromosome can be thought of as a list of customer Ids i.e. each gene of the chromosome will represent a customer location. Accordingly the length of the chromosome will be the same as the no. of customers assigned to each depot.
With this approach when we will run the Ga for depot having location 523 the length of the chromosome will be equal to 16 (no. of customers assigned) and each gene will represent the location id of the customers of depot 523.
Chromosome decoding:
We will be dividing the customers into 5 equal parts and assign them to each of the 5 lorries chronologically (as they are mentioned in the data frame). It should be noted that in this approach some lorries may remain empty or some lorry may have less no. of customers assigned to them.
This assignment can be decoded from the chromosome in the following way:
In case of depot at location id 523, we have 16 customers if we divide these 16 customers into five equal parts then each lorry should be assigned 4 customers each (in this case 16/5 = 3.2, since the result is not exact integer we round up to the next integer). This way the first 4 lorries will be assigned 4 customers each and the last lorry will remain empty i.e., it won’t be used. The first four customers from the customer list/ chromosome will be assigned to the first lorry, the next four customers to the second lorry and so on.
Population
Now that we know the encoding and decoding of the chromosome, we can create a population of a given size by randomizing the place of genes in the chromosome. The figure below shows a population of size 10.
Fitness Function
This is function is the heart of the genetic algorithm since it determines the fitness of an individual and the well being of the next generation.
In this function we will be calculating the time taken by each lorry to deliver LPG to all the customers assigned to them using the formula for calculating the dispatch time shown above with the following assumptions:
All the lorries will start and end their journey from their respective depot ( these depots are by default their nearest depot).
All the lorries will leave their respective depots at the same time thus the maximum time taken by a lorry will be the total time in which the delivery operation is completed by a specific depot in delivery LPG to its assigned customers.
The capacity of the lorry is checked before going to the next location. If the lorry capacity is less than the demand of the next location, then the lorry goes to the depot from its current location for refueling and from their it goes to the next location to make the delivery.
If the capacity of the lorry at its current location does not meet the demand of the next location then the lorry will first go to its depot for refueling and then to next location to make the delivery.
The fitness function will return the total time in which the delivery operation is completed by a specific depot in delivery LPG to its assigned customers.
Selection , Breeding and Mutation
Since we want to minimize the total time, we will prefer those individuals who displayed a lower fitness score. The selected individual will be selected for mating and a new population of individual with better characteristics than the previous generation will be produced. We will also keep swapping the positions of two customers in the chromosome/ individual with a given probability to introduce mutation.
We will repeat this process each depot for hundreds of generations to find an optimal solution to this problem with the assumption that all the lorries from all the depot will depart from their respective depot simultaneously therefore the time taken to make deliveries to all the customers of distributor company will be the maximum time taken by any of the lorry in going back to its depot to end its journey.
Using the above-described approach for 100 generations with a mutation rate of 0.4 and elite size of 7 we find that the delivery operation can be completed in 28.89 hours which is equal to 1.2 days approximately.
A glimpse of the solution is shown below.
We can see that the route came out to be such that the lorry didn’t need to refuel.
Similar blog that you make like:
If you need implementation for any of the topics mentioned above or assignment help on any of its variants, feel free to contact us.
Comments