Solving Time Constrained Vehicle Routing Problem Using Hybrid Genetic Algorithm
-
2370
Downloads
-
3771
Views
Authors
Bhawna Minocha
- Amity School of Computer Sciences, Noida, India
Saswati Tripathi
- Indian Institute of Foreign Trade, Kolkata, India
Abstract
Vehicle Routing Problem with Time windows (VRPTW) is an example of scheduling in constrained environment. It is a well known NP hard combinatorial scheduling optimization problem in which minimum number of routes have to be determined to serve all the customers within their specified time windows. So far different analytic and heuristic approaches have been tried to solve such problems. In this paper we proposed algorithms which incorporate new local search techniques with genetic algorithm approach to solve VRPTW scheduling problems in various scenarios.
Share and Cite
ISRP Style
Bhawna Minocha, Saswati Tripathi, Solving Time Constrained Vehicle Routing Problem Using Hybrid Genetic Algorithm, Journal of Mathematics and Computer Science, 3 (2011), no. 2, 192--201
AMA Style
Minocha Bhawna, Tripathi Saswati, Solving Time Constrained Vehicle Routing Problem Using Hybrid Genetic Algorithm. J Math Comput SCI-JM. (2011); 3(2):192--201
Chicago/Turabian Style
Minocha, Bhawna, Tripathi, Saswati. "Solving Time Constrained Vehicle Routing Problem Using Hybrid Genetic Algorithm." Journal of Mathematics and Computer Science, 3, no. 2 (2011): 192--201
Keywords
- Genetic algorithm
- heuristics based search techniques
- vehicle routing problem with time windows
- case- study
MSC
References
-
[1]
J. Berger, M. Barkaoui, A parallel hybrid genetic algorithm for the vehicle routing problem with time windows, Computer Operation Research, 31 (2004), 2037--2053
-
[2]
J. L. Blanton, R. L. Wainwright, Multiple vehicle routing with time and capacity constraints using genetic algorithms, Proceedings of the 5th International Conference on Genetic Algorithms, 1993 (1993), 452--459
-
[3]
O. Bräysy, M. Gendreau, Vehicle routing problem with time windows Part II: Metaheuristics, Transportation Science, 39 (2005), 119--139
-
[4]
A. Chabrier , Vehicle Routing Problem with Elementary Shortest Path based Column Generation, Computers and Operations Research, 33 (2006), 2972--2990
-
[5]
J. F. Cordeau, G. Laporte, A. Mercier, A unified tabu search heuristic for vehicle routing problems with time windows, Journal of the Operational Research Society, 52 (2001), 928--936
-
[6]
J. F. Cordeau, G. Desaulniers, J. Desrosiers, M. M. Solomon, F. Soumis, The VRP with Time Windows, in: The Vehicle Routing Problem, 2002 (2002), 157--193
-
[7]
L. M. Gambardella, E. Taillard, G. Agazzi, MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows, in: New Ideas in Optimization, 63--76, U. K. (1999)
-
[8]
J. H. Holland, Adaptation in natural and artificial systems: an introductory analysis with application to biology, University of Michigan Press, Ann Arbor (1975)
-
[9]
J. Hömberger, H. Gehring, A Two-Phase Hybrid Metaheuristic for the Vehicle Routing Problem with Time Windows, Eur. J. Oper. Res., 162 (2005), 220--238
-
[10]
B. Kallehauge, J. Larsen, O. B. G. Madsen, Lagrangean duality and non-differentiable optimization applied on routing with time windows, Computers and Operations Research, 33 (2006), 1464--1487
-
[11]
N. Kohl, J. Desrosiers, O. B. G. Madsen, M. M. Solomon, F. Soumis, 2-Path Cuts for the Vehicle Routing Problem with Time Windows, Transportation Science, 33 (1999), 101--116
-
[12]
J. Larsen , Parallelization of the vehicle routing problem with time windows, Ph.D. Thesis (Technical University of Denmark), Denmark (1999)
-
[13]
B. Ombuki, B. J. Ross, F. Hansher, Multi-objective Genetic Algorithm for Vehicle Routing Problem with Time Windows, Applied Intelligence, 24 (2006), 17--30
-
[14]
B. Minocha, S.Tripathi, Vehicle Routing Problem with Time Windows: An Evolutionary Algorithmic Approach, Algorithmic Operations Research, 1 (2006), 1--15
-
[15]
J. Potvin, S. Bengio, The Vehicle Routing Problem with Time Windows part II: Genetic Search, INFORMS Journal on Computing, 8 (1996), 165--172
-
[16]
Y. Rochat, E. Taillard, Probabilistic Diversification and Intensification in Local Search for Vehicle Routing, Journal of Heuristics, 1 (1995), 147--167
-
[17]
S. Ropke, D. Pisinger, A General Heuristics for Vehicle Routing Problems, Computers & Operations Research, 34 (2007), 2403--2435
-
[18]
P. Shaw, Using Constraint Programming and Local Search Methods to solve Vehicle Routing Problems, International conference on principles and practice of constraint programming, 1998 (1998), 417--431
-
[19]
M. M. Solomon, Algorithms for Vehicle Routing and Scheduling Problems with Time Window Constraints, Operations Research, 35 (1987), 254--265
-
[20]
E. D. Taillard, P. Badeau, M. Gendreau, F. Guertin, J. Potvin, A Tabu Search Heuristics for the Vehicle Routing Problem with Soft Time Windows, Transportation Science, 31 (1997), 170--186
-
[21]
K. C. Tan, L. H. Lee, K. Ou, Hybrid Genetic Algorithms in Solving Vehicle Routing Problems with Time Window Constraint, Asia-Pacific Journal of Operation Research, 18 (2001), 121--130
-
[22]
S. R. Thangiah, Vehicle Routing with Time Windows using Genetic Algorithms, In: Application Handbook of Genetic Algorithms: New Frontiers, 1995 (1995), 253--277