Genetic Algorithm for Dial-a-Ride Problem
undefined
Application of a genetic
algorithm for solving the Dial-a-
Ride problem
S
T
J
E
P
A
N
Z
E
L
I
Ć
,
M
A
R
K
O
Đ
U
R
A
S
E
V
I
Ć
,
D
O
M
A
G
O
J
J
A
K
O
B
O
V
I
Ć
,
L
U
C
I
J
A
P
L
A
N
I
N
I
Ć
UNIVERSITY OF ZAGREB FACULTY OF ELECTRICAL ENGINEERING AND COMPUTING
Overview
•
Introduction to the Dial-a-Ride Problem
•
Adaptation of a Genetic Algorithm
•
Experimental setup
•
Results
•
Conclusion and future work
2
Introduction
•
Dial-a-Ride problem (DARP) is a specific variant of VRP
•
Tasked with transportation of people instead of goods
•
Many applications in the real world
•
Transportation of elderly or disabled people
•
Taxi services
•
Rescue services
•
Demand-responsive transit
3
Dial-a-Ride Problem
4
Dial-a-Ride Problem
5
Solution representation
•
Solution consists out of 2 arrays:
•
Integer array -> denotes the association of each order to a vehicle
•
Permutation array -> denotes the order in which the customers are served
6
Solution initialisation
7
PMX crossover variant
8
Car change mutation
9
Solution infeasibility
•
Solutions can become infeasible in certain occasions (after application
of genetic operators)
•
Several solution repairing procedures are used
•
Order of pick-ups and drop-offs
•
Vehicle capacity
•
Pickup and delivery in the same vehicle
10
GA parameters
•
Population: 200 individuals
•
Mutation probability:
10
%
•
5-tournament selection
•
stopping criterion: 1500 generations
•
Generation GA with 4% elitism
•
Performs mutation of population if individuals become too similar
11
Experimental setup
•
20 problem instances
•
Between 48 and 288 requests per instance
•
Between 3 and 13 vehicles per instance
•
Instances R1a-R10a – narrow time windows
•
Instances R1b-R10b– wide time windows
12
Results
•
Comparison with two previous studies:
•
Cordeau and Laporte
[1]
•
Hard constraints
•
Tabu search
•
Jorgensen et al.
[2]
•
Soft constraints
•
Genetic algorithm
•
Results
•
Blue – better than Cordeau and Laporte
•
Yellow - better than Jorgensen
•
Green – better than both
•
Red – worse than both
•
White – instances not used in previous studies
13
Results
14
Results - overview
•
Better results always achieved for vehicle waiting time
•
Differences usually large (factor of 3)
•
The proposed algorithm usually better in 2 out of 3 criteria
•
Differences on other two criteria are small (at most 5%)
•
The late times are not available for previous studies
•
The late times were usually around a few minutes
•
Can be considered acceptable for the customers
15
Conclusion
•
Comparable or better results to those of a previous study
•
Benefit of modeling hard constraints as soft
•
More flexibility
•
Low values for objectives which represent those constraints
•
Many areas for improvement of the algorithm
16
Future research
•
Multi-objective optimisation (NSGA-II, NSGA-III and similar)
•
Extend to other DARP variants
•
Dynamic variant (not all requests are known up front) -> hyperheuristics
•
Customers can change vehicles
•
Combination with local search operators for improving solutions
17
Questions?
•
Thank you for your attention!
•
Questions?
18
References
[1]
Cordeau, J.F., Laporte, G.: A tabu search heuristic for the static multi-
vehicle
dial-a-ride problem. Transportation Research Part B:
Methodological 37(6),
579–594 (2003).
[2] J
orgensen, R., Larsen, J., Bergvinsdottir, K.: Solving the dial-a-
ride problem using
genetic algorithms. Journal of the Operational
Research Society 5 (2007).
19
The study explores the application of a genetic algorithm to solve the Dial-a-Ride problem, a variant of the Vehicle Routing Problem tailored for transporting people. It delves into problem introduction, algorithm adaptation, experimental setup, results, and future implications. The problem entails optimizing criteria such as route duration, ride time, wait time, late time, ride time violation, and route violation. Solutions are represented through arrays denoting order association and customer service sequence, with initializations employing greedy random techniques for enhanced performance.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Application of a genetic algorithm for solving the Dial-a- Ride problem STJEPAN ZELI , MARKO MARKO URASEVI URASEVI , DOMAGOJ JAKOBOVI , LUCIJA PLANINI UNIVERSITY OF ZAGREB FACULTY OF ELECTRICAL ENGINEERING AND COMPUTING
Overview Introduction to the Dial-a-Ride Problem Adaptation of a Genetic Algorithm Experimental setup Results Conclusion and future work 2
Introduction Dial-a-Ride problem (DARP) is a specific variant of VRP Tasked with transportation of people instead of goods Many applications in the real world Transportation of elderly or disabled people Taxi services Rescue services Demand-responsive transit 3
Dial-a-Ride Problem Customers: Request for a pick up at a certain location Request to be dropped off at a certain location Have a time window in which they should be picked up or delivered [??,??] Have a maximum ride time request Service time required at each location Vehicles Have a certain capacity (number of passengers) Have a maximum driving time Start and end their route at the depot 4
Dial-a-Ride Problem Optimisation criteria: ?1- total route duration ?2 - total ride time ?3 - total wait time ?4 - total late time ?5 - total ride time violation ?6 - total maximum route violation Total criterion: ? = ?1+ ?2+ ?3+ 5?4+ 5?5+ 5?6 5
Solution representation Solution consists out of 2 arrays: Integer array -> denotes the association of each order to a vehicle Permutation array -> denotes the order in which the customers are served 6
Solution initialisation Greedy random initialisation The permutation of orders is randomly generated A heuristic is applied to allocate each vehicle to each customer The vehicle which can arrive the closest to the middle of the time window for a customer is chosen: ??=?? ?? Preliminary experiments showed a better performance in comparison with completely random initialisation 2 7
Solution infeasibility Solutions can become infeasible in certain occasions (after application of genetic operators) Several solution repairing procedures are used Order of pick-ups and drop-offs Vehicle capacity Pickup and delivery in the same vehicle 10
GA parameters Population: 200 individuals Mutation probability: 10% 5-tournament selection stopping criterion: 1500 generations Generation GA with 4% elitism Performs mutation of population if individuals become too similar 11
Experimental setup 20 problem instances Between 48 and 288 requests per instance Between 3 and 13 vehicles per instance Instances R1a-R10a narrow time windows Instances R1b-R10b wide time windows 12
Results Comparison with two previous studies: Cordeau and Laporte [1] Hard constraints Tabu search Jorgensen et al. [2] Soft constraints Genetic algorithm Results Blue better than Cordeau and Laporte Yellow - better than Jorgensen Green better than both Red worse than both White instances not used in previous studies 13
Results Route Duration Vehicle Waiting Time Ride Time Best Problem R1a R2a R3a R4a R5a R6a R7a R8a R9a R10a R1b R2b R3b R4b R5b R6b R7b R8b R9b R10b Total * Avg. Avg. Best Avg. 1138 2190 Best Best Avg. Late Time 0.48595683 0.72425273 0.344888407 0.529672435 0.97634376 0.924522088 1.49871474 0.888685602 4.718814796 5.185603279 0.482367647 0.420772778 0.338342375 0.197928391 0.584174884 1.125918783 0.538261459 0.960419878 1.87709699 3.618267801 21.08272015 Best Avg. Ride Time Violation 890 1601 2353.5 2386.7 117.25 92.546 3486.8 2957.6 3251.9 3598.5 269.71 547.53 4635.1 4494.5 3812.8 3958.1 193.02 316.91 5885.1 4789.7 4690.7 4773 279.24 322.58 7228.2 7133.2 1273 1353.7 133.13 161.56 2270.6 2254.3 45.818 14.286 3348.6 2802.5 3225.4 3304.5 64.377 117.84 5834.6 5947.4 4422.3 4517.9 96.778 102.31 8099.3 7795.5 788 765.54 31.309 3.5452 984.11 666.82 1498.9 1422 54.698 5.5902 2107.7 1733.1 2306.4 2282 68.717 34.193 3369.6 2554.8 3001 2940.9 75.223 37.503 4352.6 3635.5 3749 3981.2 135.48 242.11 5618.1 5129.8 4492 4456 148.8 138.85 6653.4 6170.7 1150.3 1119.8 19.2 9.7416 1570.7 1357.6 2328.6 2355 99.637 88.487 3504.5 2658.1 3287.1 3336.7 45.28 89.962 5961.7 5414.9 4388.3 4442 65.622 70.394 7734.1 7084.3 35659 36637 1249 972 1975 114 164 201 491 694 1969 0.07394674 1.59624029 0.918569627 1.204654246 1.323063408 2.578248611 0.194605793 2.861205659 2.516191584 4.264299874 0.055866058 1.322663886 0.41843259 0.817551003 1.3365416 1.013345061 1.122871983 2.17390812 2.982317569 1.998619899 20.52453758 1571 1295.4 1882 57264 51711 14
Results - overview Better results always achieved for vehicle waiting time Differences usually large (factor of 3) The proposed algorithm usually better in 2 out of 3 criteria Differences on other two criteria are small (at most 5%) The late times are not available for previous studies The late times were usually around a few minutes Can be considered acceptable for the customers 15
Conclusion Comparable or better results to those of a previous study Benefit of modeling hard constraints as soft More flexibility Low values for objectives which represent those constraints Many areas for improvement of the algorithm 16
Future research Multi-objective optimisation (NSGA-II, NSGA-III and similar) Extend to other DARP variants Dynamic variant (not all requests are known up front) -> hyperheuristics Customers can change vehicles Combination with local search operators for improving solutions 17
Questions? Thank you for your attention! Questions? 18
References [1] Cordeau, J.F., Laporte, G.: A tabu search heuristic for the static multi- vehicle dial-a-ride problem. Transportation Research Part B: Methodological 37(6), 579 594 (2003). [2] Jorgensen, R., Larsen, J., Bergvinsdottir, K.: Solving the dial-a- ride problem using genetic algorithms. Journal of the Operational Research Society 5 (2007). 19
