Towards the solution of variants of Vehicle Routing Problem

Dr. Pawan Jindal
Dr. Pawan Jindal * §
Contact
§ Jaypee University of Engineering & Technology, Guna, M.P. India. Jaypee University of Engineering & Technology, Guna,...

Send Message

To: Author

Towards the solution of variants of Vehicle Routing Problem

Article Fingerprint

ReserarchID

CST0812G

Towards the solution of variants of Vehicle Routing Problem Banner

Key Research Insights

Synthesized scholarly intelligence & interactive research assistant
Access Review Comments
  • English
  • Afrikaans
  • Albanian
  • Amharic
  • Arabic
  • Armenian
  • Azerbaijani
  • Basque
  • Belarusian
  • Bengali
  • Bosnian
  • Bulgarian
  • Catalan
  • Cebuano
  • Chichewa
  • Chinese (Simplified)
  • Chinese (Traditional)
  • Corsican
  • Croatian
  • Czech
  • Danish
  • Dutch
  • Esperanto
  • Estonian
  • Filipino
  • Finnish
  • French
  • Frisian
  • Galician
  • Georgian
  • German
  • Greek
  • Gujarati
  • Haitian Creole
  • Hausa
  • Hawaiian
  • Hebrew
  • Hindi
  • Hmong
  • Hungarian
  • Icelandic
  • Igbo
  • Indonesian
  • Irish
  • Italian
  • Japanese
  • Javanese
  • Kannada
  • Kazakh
  • Khmer
  • Korean
  • Kurdish (Kurmanji)
  • Kyrgyz
  • Lao
  • Latin
  • Latvian
  • Lithuanian
  • Luxembourgish
  • Macedonian
  • Malagasy
  • Malay
  • Malayalam
  • Maltese
  • Maori
  • Marathi
  • Mongolian
  • Myanmar (Burmese)
  • Nepali
  • Norwegian
  • Pashto
  • Persian
  • Polish
  • Portuguese
  • Punjabi
  • Romanian
  • Russian
  • Samoan
  • Scots Gaelic
  • Serbian
  • Sesotho
  • Shona
  • Sindhi
  • Sinhala
  • Slovak
  • Slovenian
  • Somali
  • Spanish
  • Sundanese
  • Swahili
  • Swedish
  • Tajik
  • Tamil
  • Telugu
  • Thai
  • Turkish
  • Ukrainian
  • Urdu
  • Uzbek
  • Vietnamese
  • Welsh
  • Xhosa
  • Yiddish
  • Yoruba
  • Zulu
Reading Preferences
Font Size
Line Spacing
Background
This converted HTML version may contain rendering inconsistencies. Please refer to the PDF for the authoritative version, or click here to provide feedback.

Abstract

Some of the problems that are used extensively in real life are NP complete problems. There is no any algorithm which can give the optimal solution to NP complete problems in the polynomial time in the worst case. So researchers are applying their best efforts to design the approximation algorithms for these NP complete problems. Approximation algorithm gives the solution of a particular problem, which is close to the optimal solution of that problem. In this paper, a study on variants of vehicle routing problem is being done along with the difference in the approximation ratios of different approximation algorithms as being given by researchers and it is found that Researchers are continuously applying their best efforts to design new approximation algorithms which have better approximation ratio as compared to the previously existing algorithms.

References

70 Cites in Article
  1. E Reingold,J Nievergelt,N Deo (1977). Combinatorial Algorithms: Theory and Practice.
  2. J Allahverdi,T Gupta,Aldowaisan (1999). A review of scheduling research involving setupconsiderations.
  3. Esther Arkin,Joseph Mitchell,Giri Narasimhan (1998). Resource-constrained geometric network optimization.
  4. B Awerbuch,Y Azar,A Blum,S Vempala (1999). Improved approximation guarantees for minimumweight k-trees and prizecollecting salesmen.
  5. Reuven Bar-Yehuda,Guy Even,Shimon Shahar (2003). On approximating a geometric prize-collecting traveling salesman problem with time windows.
  6. A Blum,S Chawla,D Karger,T Lane,A Meyerson,M Minkoff (2003). Approximation algorithms for orienteering and discounted-reward TSP.
  7. J Bruno,P Downey (1978). Complexity of task sequencing with deadlines, set-up times and changeover costs.
  8. G Frederickson,B Wittman (2007). Approximation algorithms for the traveling repairman and speeding deliveryman problems with unit-time windows.
  9. M Desrochers,J Desrosiers,M Solomon (1992). A new optimization algorithm for the vehicle routing problem with time windows.
  10. J Desrosiers,F Soumis,M Desrochers,M Sauvé (1988). Vehicle routing and scheduling with time windows.
  11. Bruce Golden,Larry Levy,Rakesh Vohra (1987). The orienteering problem.
  12. Marc Gravel,Wilson Price,Caroline Gagné (2000). Scheduling jobs in an Alcan aluminium foundry using a genetic algorithm.
  13. C Jordan (1998). A two-phase genetic algorithm to solve variants of the batch sequencing problem.
  14. Marisa Kantor,Moshe Rosenwein (1992). The Orienteering Problem with Time Windows.
  15. Y Karuno,H Nagamochi (2001). A 2-approximation algorithm for the multi-vehicle scheduling problem on a path with release and handling times.
  16. A Kolen,A Rinnooy Kan,H Trienekens (1987). Vehicle Routing with Time Windows.
  17. Sam Thangiah (1995). Vehicle Routing with Time Windows using Genetic Algorithms.
  18. K Tan,L Lee,K Zhu (2000). Heuristic methods for vehicle routing problem with time windows.
  19. M Savelsbergh (1985). Local search in routing problems with time windows.
  20. Sam Thangiah,Ibrahim Osman,Rajini Vinayagamoorthy,Tong Sun (1993). Algorithms for the Vehicle Routing Problems with Time Deadlines.
  21. John Tsitsiklis (1992). Special cases of traveling salesman and repairman problems with time windows.
  22. Joel Wisner,S Siferd (1995). A study of US machine shops with just‐in‐time customers.
  23. Wen-Hwa Yang,C Liao (1999). Survey of scheduling research involving setup times.
  24. Nikhil Bansal,Avrim Blum,Shuchi Chawla,Adam Meyerson (2004). Approximation algorithms for deadline-TSP and vehicle routing with time-windows.
  25. R Ahuja,T Magnanti,J Orlin (1993). Network Flows: Theory, Algorithms, and Applications.
  26. Esther Arkin,Joseph Mitchell,Giri Narasimhan (1998). Resource-constrained geometric network optimization.
  27. S Arora,G Karakostas (2000). A 2 + ε approximation algorithm for the k-MST problem.
  28. Baruch Awerbuch,Yossi Azar,Avrim Blum,Santosh Vempala (1995). Improved approximation guarantees for minimum-weight <i>k</i>-trees and prize-collecting salesmen.
  29. Egon Balas (1989). The prize collecting traveling salesman problem.
  30. A Frieze,G Galbiati,F Maffioli (1982). On the worst‐case performance of some algorithms for the asymmetric traveling salesman problem.
  31. R Bar-Yehuda,G Even,S Shahar (2003). On approximating a geometric prize-collecting traveling salesman problem with time windows.
  32. N Garg (1996). A 3-approximation for the minimum tree spanning k vertices.
  33. Avrim Blum,R Ravi,Santosh Vempala (1996). A Constant-Factor Approximation Algorithm for thek-MST Problem.
  34. K Chaudhuri,B Godfrey,S Rao,K Talwar (2003). Paths, trees, and minimum latency tours.
  35. C Chekuri,A Kumar (2004). Maximum coverage problem with group budget constraints and applications.
  36. C Chekuri,M Pal (2005). A Recursive Greedy Algorithm for Walks in Directed Graphs.
  37. C Chekuri,M (2005). An O(log n) Approximation for the Asymmetric Traveling Salesman Path Problem Theory of Computing.
  38. Naveen Garg (2005). Saving an epsilon.
  39. Michel Goemans,David Williamson (1995). A General Approximation Technique for Constrained Forest Problems.
  40. Bruce Golden,Larry Levy,Rakesh Vohra (1987). The orienteering problem.
  41. G Gutin,A Punnen (2002). The Traveling Salesman Problem and Its Variations.
  42. C Chekuri,N Korula,M P´al (2008). Improved Algorithms for Orienteering and Related Problems.
  43. E Lawler,A Rinnooy Kan,J Lenstra,D Shmoys (1985). The Traveling salesman problem: a guided tour of combinatorial optimization.
  44. Viswanath Nagarajan,R Ravi (2007). Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems.
  45. Paolo Toth,Daniele Vigo (2001). Models, relaxations and exact approaches for the capacitated vehicle routing problem.
  46. J Tsitsiklis (1992). Special cases of traveling salesman and repairman problems with time windows.
  47. K Chen,S Har-Peled (2006). The orienteering problem in the plane revisited.
  48. E Horowitz,S Sahni (1982). Fundamental of Computer Algorithms.
  49. T Cormen,C Leiserson,R Rivest (1991). Introduction to Algorithms.
  50. A Aho,J Hopcroft,J Ullman (1974). The Design and Analysis of Computer Algorithms.
  51. A Aho,J Hopcroft,J Ullman (1984). Data Structures and Algorithms.
  52. S Baase (1988). Computer Algorithms: Introduction to Design and Analysis.
  53. L Banachowski,A Kreczmar,W Rytter (1991). Analysis of Algorithms and Data Structures.
  54. Ricardo Baeza-Yates (1995). Teaching algorithms.
  55. Gerard Tel (1995). Introduction to Distributed Algorithms.
  56. G-Brassard,P Bratley (1988). Algorithmics: Theory and Practice.
  57. Bruce Golden,Arjang Assad,Edward Wasil (1986). Introduction.
  58. (1988). Vehicle Routing with Time Windows: Optimization and Approximation.
  59. (1995). Time constrained routing and scheduling.
  60. J-F Cordeau,G Laporte,A Mercier (2001). A unified tabu search heuristic for vehicle routing problems with time windows.
  61. J Larsen (1999). Parallelization of the Vehicle Routing Problem with TimeWindows.
  62. Malek Alzaqebah,Sana Jawarneh,Hafiz Sarim,Salwani Abdullah (1999). Bees Algorithm for Vehicle Routing Problems with Time Windows.
  63. B Fleischmann (1990). The vehicle routing problem with multiple use of vehicles.
  64. E Taillard,G Laporte,M Gendreau (1996). Vehicle routing with multiple use of vehicles.
  65. Ann Campbell,Martin Savelsbergh (2004). Efficient Insertion Heuristics for Vehicle Routing and Scheduling Problems.
  66. W Chiang,R Russell (1996). Simulated annealing metaheuristics for the vehicle routing problem with time windows.
  67. Liong Choong Yeun,Wan Ismail,Khairuddin Omar2,Mourad Zirour (2008). Vehicle Routing Problem: Models and Solutions Journal of Quality Measurement and Analysis.
  68. G King,C Mast (1997). Excess Travel: Causes, Extent and Consequences.
  69. Teodor Crainic,Gilbert Laporte (1997). Planning models for freight transportation.
  70. Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms.
Show All References
Download References

Funding

No external funding was declared for this work.

Conflict of Interest

The authors declare no conflict of interest.

Ethical Approval

No ethics committee approval was required for this article type.

Data Availability

Not applicable for this article.

How to Cite This Article

Dr. Pawan Jindal. 1970. "Towards the solution of variants of Vehicle Routing Problem". Global Journal of Computer Science and Technology GJCST Volume 11 (GJCST Volume 11 Issue 15).

More Citation Formats

Download Citation

  • Open Access
  • CC-BY-ND-NC 4.0
Download Article
Access OJS
Journal Specifications

Crossref Journal DOI 10.17406/gjcst

Print ISSN 0975-4350

e-ISSN 0975-4172

Keywords
Approximation algorithmsNP completenessVehicle Routing problem with time widows
Classification
GJCST Classification C.2.2
  • Submission ReceivedJuly 22, 2011
  • Peer Review Double Blind
    Handling Editor
  • Accepted August 17, 2011
  • Published September 1, 2011
Version of record

v1.2

Issue date
September 7, 2011

Language
English
Order Article Reprint
Experiance in AR

Explore published articles in an immersive Augmented Reality environment. Our platform converts research papers into interactive 3D books, allowing readers to view and interact with content using AR and VR compatible devices.

View in VR
Read in 3D

Your published article is automatically converted into a realistic 3D book. Flip through pages and read research papers in a more engaging and interactive format.

View in 3D
Article Matrices
Total Views: 5.8K
Total Downloads: 498
All Trends

Request Access

Please fill out the form below to request access to this research paper. Your request will be reviewed by the editorial or author team.
X

This is the heading

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.

High-quality academic research articles on global topics and journals.

Towards the solution of variants of Vehicle Routing Problem

Dr. Jindal
Dr. Jindal Jaypee University of Engineering & Technology, Guna, M.P. India.
  • Submission ReceivedJuly 22, 2011
  • Peer Review Double Blind
    Handling Editor
  • Accepted August 17, 2011
  • Published September 1, 2011