Processing, Please wait...

  • Home
  • About Us
  • Search:
  • Advanced Search

Growing Science » International Journal of Industrial Engineering Computations » A hybrid metaheuristic for the time-dependent vehicle routing problem with hard time windows

Journals

  • IJIEC (747)
  • MSL (2643)
  • DSL (668)
  • CCL (508)
  • USCM (1092)
  • ESM (413)
  • AC (562)
  • JPM (271)
  • IJDS (912)
  • JFS (96)
  • HE (32)
  • SCI (26)

IJIEC Volumes

    • Volume 1 (17)
      • Issue 1 (9)
      • Issue 2 (8)
    • Volume 2 (68)
      • Issue 1 (12)
      • Issue 2 (20)
      • Issue 3 (20)
      • Issue 4 (16)
    • Volume 3 (76)
      • Issue 1 (9)
      • Issue 2 (15)
      • Issue 3 (20)
      • Issue 4 (12)
      • Issue 5 (20)
    • Volume 4 (50)
      • Issue 1 (14)
      • Issue 2 (10)
      • Issue 3 (12)
      • Issue 4 (14)
    • Volume 5 (47)
      • Issue 1 (13)
      • Issue 2 (12)
      • Issue 3 (12)
      • Issue 4 (10)
    • Volume 6 (39)
      • Issue 1 (7)
      • Issue 2 (12)
      • Issue 3 (10)
      • Issue 4 (10)
    • Volume 7 (47)
      • Issue 1 (10)
      • Issue 2 (14)
      • Issue 3 (10)
      • Issue 4 (13)
    • Volume 8 (30)
      • Issue 1 (9)
      • Issue 2 (7)
      • Issue 3 (8)
      • Issue 4 (6)
    • Volume 9 (32)
      • Issue 1 (9)
      • Issue 2 (6)
      • Issue 3 (7)
      • Issue 4 (10)
    • Volume 10 (34)
      • Issue 1 (8)
      • Issue 2 (10)
      • Issue 3 (8)
      • Issue 4 (8)
    • Volume 11 (36)
      • Issue 1 (9)
      • Issue 2 (8)
      • Issue 3 (9)
      • Issue 4 (10)
    • Volume 12 (29)
      • Issue 1 (9)
      • Issue 2 (6)
      • Issue 3 (8)
      • Issue 4 (6)
    • Volume 13 (41)
      • Issue 1 (10)
      • Issue 2 (8)
      • Issue 3 (10)
      • Issue 4 (13)
    • Volume 14 (50)
      • Issue 1 (11)
      • Issue 2 (15)
      • Issue 3 (9)
      • Issue 4 (15)
    • Volume 15 (55)
      • Issue 1 (19)
      • Issue 2 (15)
      • Issue 3 (12)
      • Issue 4 (9)
    • Volume 16 (75)
      • Issue 1 (12)
      • Issue 2 (15)
      • Issue 3 (19)
      • Issue 4 (29)
    • Volume 17 (21)
      • Issue 1 (21)

Keywords

Supply chain management(166)
Jordan(161)
Vietnam(149)
Customer satisfaction(120)
Performance(113)
Supply chain(111)
Service quality(98)
Competitive advantage(95)
Tehran Stock Exchange(94)
SMEs(87)
optimization(86)
Trust(83)
TOPSIS(83)
Financial performance(83)
Sustainability(82)
Job satisfaction(80)
Factor analysis(78)
Social media(78)
Artificial intelligence(77)
Knowledge Management(77)


» Show all keywords

Authors

Naser Azad(82)
Mohammad Reza Iravani(64)
Zeplin Jiwa Husada Tarigan(63)
Endri Endri(45)
Muhammad Alshurideh(42)
Hotlan Siagian(39)
Jumadil Saputra(36)
Dmaithan Almajali(36)
Muhammad Turki Alshurideh(35)
Barween Al Kurdi(32)
Ahmad Makui(32)
Basrowi Basrowi(31)
Hassan Ghodrati(31)
Mohammad Khodaei Valahzaghard(30)
Sautma Ronni Basana(29)
Shankar Chakraborty(29)
Ni Nyoman Kerti Yasa(29)
Sulieman Ibraheem Shelash Al-Hawary(28)
Prasadja Ricardianto(28)
Haitham M. Alzoubi(27)


» Show all authors

Countries

Iran(2184)
Indonesia(1290)
India(788)
Jordan(786)
Vietnam(504)
Saudi Arabia(453)
Malaysia(441)
United Arab Emirates(220)
China(206)
Thailand(153)
United States(111)
Turkey(106)
Ukraine(104)
Egypt(98)
Canada(92)
Peru(88)
Pakistan(85)
United Kingdom(80)
Morocco(79)
Nigeria(78)


» Show all countries

International Journal of Industrial Engineering Computations

ISSN 1923-2934 (Online) - ISSN 1923-2926 (Print)
Quarterly Publication
Volume 8 Issue 1 pp. 141-160 , 2017

A hybrid metaheuristic for the time-dependent vehicle routing problem with hard time windows Pages 141-160 Right click to download the paper Download PDF

Authors: N. Rincon-Garcia, B.J. Waterson, T.J. Cherrett

DOI: 10.5267/j.ijiec.2016.6.002

Keywords: Vehicle routing problem, Time-dependent travel time, Hybrid metaheuristic algorithm

Abstract: This article paper presents a hybrid metaheuristic algorithm to solve the time-dependent vehicle routing problem with hard time windows. Time-dependent travel times are influenced by different congestion levels experienced throughout the day. Vehicle scheduling without consideration of congestion might lead to underestimation of travel times and consequently missed deliveries. The algorithm presented in this paper makes use of Large Neighbourhood Search approaches and Variable Neighbourhood Search techniques to guide the search. A first stage is specifically designed to reduce the number of vehicles required in a search space by the reduction of penalties generated by time-window violations with Large Neighbourhood Search procedures. A second stage minimises the travel distance and travel time in an ‘always feasible’ search space. Comparison of results with available test instances shows that the proposed algorithm is capable of obtaining a reduction in the number of vehicles (4.15%), travel distance (10.88%) and travel time (12.00%) compared to previous implementations in reasonable time.

How to cite this paper
Rincon-Garcia, N., Waterson, B & Cherrett, T. (2017). A hybrid metaheuristic for the time-dependent vehicle routing problem with hard time windows.International Journal of Industrial Engineering Computations , 8(1), 141-160.

Refrences
Bräysy, O. (2003). A reactive variable neighborhood search for the vehicle-routing problem with time windows. INFORMS Journal on Computing, 15(4), 347-368.
Bräysy, O., & Gendreau, M. (2005a). Vehicle routing problem with time windows, Part I: Route construction and local search algorithms. Transportation science, 39(1), 104-118.
Bräysy, O., & Gendreau, M. (2005b). Vehicle routing problem with time windows, Part II: Metaheuristics. Transportation science, 39(1), 119-139.
Bräysy, O., & Hasle, G. (2014). Software Tools and Emerging Technologies for Vehicle Routing and Intermodal Transportation. Vehicle Routing: Problems, Methods, and Applications, 18, 351.
Chang, Y. S., Lee, Y. J., & Choi, S. B. (2015). More Traffic Congestion in Larger Cities?-Scaling Analysis of the Large 101 US Urban Centers.
Chopra, S., & Meindl, P. (2007). Supply chain management. Strategy, planning & operation: Springer.
Cordeau, J.-F., Gendreau, M., Laporte, G., Potvin, J.-Y., & Semet, F. (2002). A guide to vehicle routing heuristics. Journal of the Operational Research society, 53(5), 512-522.
Dabia, S., Ropke, S., Van Woensel, T., & De Kok, T. (2013). Branch and price for the time-dependent vehicle routing problem with time windows. Transportation science, 47(3), 380-396.
DFT. (2010). Integrated Research Study: HGV Satellite Navigation and Route Planning. Retrieved April 01, 2013, from http://www.freightbestpractice.org.uk/products/3705_7817_integrated-research-study--hgv-satellite-navigation-and-route-planning.aspx.
Donati, A. V., Montemanni, R., Casagrande, N., Rizzoli, A. E., & Gambardella, L. M. (2008). Time dependent vehicle routing problem with a multi ant colony system. European journal of operational research, 185(3), 1174-1191.
Drexl, M. (2012). Rich vehicle routing in theory and practice. Logistics Research, 5(1-2), 47-63.
Eglese, R., Maden, W., & Slater, A. (2006). A road timetableTM to aid vehicle routing and scheduling. Computers & operations research, 33(12), 3508-3519.
Ehmke, J. F., Steinert, A., & Mattfeld, D. C. (2012). Advanced routing for city logistics service providers based on time-dependent travel times. Journal of Computational Science, 3(4), 193-205.
Figliozzi, M. A. (2012). The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics. Transportation Research Part E-Logistics and Transportation Review, 48(3), 616-636. doi: DOI 10.1016/j.tre.2011.11.006
Fleischmann, B., Gietz, M., & Gnutzmann, S. (2004). Time-varying travel times in vehicle routing. Transportation science, 38(2), 160-173.
FTA. (2015). Logistics Report 2015.Delivering Safe, Efficient, Sustainable Logistics. In FTA (Ed.), About. Tunbridge Wells: FTA.
Gendreau, M., Ghiani, G., & Guerriero, E. (2015). Time-dependent routing problems: A review. Computers & operations research, 64, 189-197.
Golden, B., Wasil, E., Kelly, J., & Chao, I. (1998). Fleet Management and Logistics, chapter The Impact of Metaheuristics on Solving the Vehicle Routing Problem: algorithms, problem sets, and computational results: Kluwer Academic Publishers, Boston.
Haghani, A., & Jung, S. (2005). A dynamic vehicle routing problem with time-dependent travel times. Computers & operations research, 32(11), 2959-2986.
Hallamaki, A., Hotokka, P., Brigatti, J., Nakari, P., Bräysy, O., & T, R. (2007). Vehicle Routing Software: A Survey and Case Studies with Finish Data. Technical Report. Finland: University of Jyväskylä.
Hansen, P., & Mladenović, N. (2001). Variable neighborhood search: Principles and applications. European journal of operational research, 130(3), 449-467.
Hansen, P., Mladenović, N., & Pérez, J. A. M. (2010). Variable neighbourhood search: methods and applications. Annals of Operations Research, 175(1), 367-407.
Ichoua, S., Gendreau, M., & Potvin, J.-Y. (2003). Vehicle dispatching with time-dependent travel times. European journal of operational research, 144(2), 379-396.
IMRG. (2012). UK valuing home delivery review 2012. In IMRG (Ed.).
Javelin-Group. (2011). How many stores will we really need? UK non-food retailing in 2020. In L. J. Group. (Ed.).
Jiang, J., Ng, K. M., Poh, K. L., & Teo, K. M. (2014). Vehicle routing problem with a heterogeneous fleet and time windows. Expert Systems with Applications, 41(8), 3748-3760.
Kok, A., Hans, E., & Schutten, J. (2012). Vehicle routing under time-dependent travel times: the impact of congestion avoidance. Computers & operations research, 39(5), 910-918.
Kritzinger, S., Tricoire, F., Doerner, K. F., & Hartl, R. F. (2011). Variable neighborhood search for the time-dependent vehicle routing problem with soft time windows Learning and Intelligent Optimization (pp. 61-75): Springer.
Kytöjoki, J., Nuortio, T., Bräysy, O., & Gendreau, M. (2007). An efficient variable neighborhood search heuristic for very large scale vehicle routing problems. Computers & operations research, 34(9), 2743-2757.
Liu, F.-H., & Shen, S.-Y. (1999). The fleet size and mix vehicle routing problem with time windows. Journal of the Operational Research society, 721-732.
Malandraki, C. (1989). Time dependent vehicle routing problems: Formulations, solution algorithms and computational experiments.
Malandraki, C., & Daskin, M. S. (1992). Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms. Transportation science, 26(3), 185-200.
Mattos Ribeiro, G., & Laporte, G. (2012). An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem. Computers & operations research, 39(3), 728-735.
Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & operations research, 24(11), 1097-1100.
Nagata, Y., Bräysy, O., & Dullaert, W. (2010). A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. Computers & operations research, 37(4), 724-737.
Pisinger, D., & Ropke, S. (2007). A general heuristic for vehicle routing problems. Computers & operations research, 34(8), 2403-2435.
Polacek, M., Hartl, R. F., Doerner, K., & Reimann, M. (2004). A variable neighborhood search for the multi depot vehicle routing problem with time windows. Journal of heuristics, 10(6), 613-627.
Rincon-Garcia, N., Waterson , B. J., & Cherret, T. J. (2015). Requirements from Vehicle Routing Software: Perspectives from literature, developers and the freight industry. Under Review.
Ropke, S., & Pisinger, D. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation science, 40(4), 455-472.
Schrimpf, G., Schneider, J., Stamm-Wilbrandt, H., & Dueck, G. (2000). Record breaking optimization results using the ruin and recreate principle. Journal of Computational Physics, 159(2), 139-171.
Shaw, P. (1997). A new local search algorithm providing high quality solutions to vehicle routing problems. APES Group, Dept of Computer Science, University of Strathclyde, Glasgow, Scotland, UK.
Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems Principles and Practice of Constraint Programming—CP98 (pp. 417-431): Springer.
Solomon, M. M. (1987). Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints Operations Research, 35(2), 254-265.
Sörensen, K. (2015). Metaheuristics—the metaphor exposed. International Transactions in Operational Research, 22(1), 3-18.
Toth, P., & Vigo, D. (2001). The vehicle routing problem: Siam.
US-Department-Of-Transport. (2003). Final Report -Traffic Congestion and Reliability: Linking Solutions to Problems.
Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2013). A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows. Computers & operations research, 40(1), 475-489.
Visser, J., Nemoto, T., & Browne, M. (2014). Home delivery and the impacts on urban freight transport: A review. Procedia-social and behavioral sciences, 125, 15-27.
Zachariadis, E. E., & Kiranoudis, C. T. (2010). A strategy for reducing the computational complexity of local search-based methods for the vehicle routing problem. Computers & operations research, 37(12), 2089-2105.
  • 17
  • 1
  • 2
  • 3
  • 4
  • 5

Journal: International Journal of Industrial Engineering Computations | Year: 2017 | Volume: 8 | Issue: 1 | Views: 2946 | Reviews: 0

Related Articles:
  • Vehicle routing problem with considering multi-middle depots for perishable ...
  • Integrating packing and distribution problems and optimization through math ...
  • A new memetic algorithm for solving split delivery vehicle routing problem
  • A generalized multi-depot vehicle routing problem with replenishment based ...
  • Route activity tracking and management using available technology

Add Reviews

Name:*
E-Mail:
Review:
Bold Italic Underline Strike | Align left Center Align right | Insert smilies Insert link URLInsert protected URL Select color | Add Hidden Text Insert Quote Convert selected text from selection to Cyrillic (Russian) alphabet Insert spoiler
winkwinkedsmileam
belayfeelfellowlaughing
lollovenorecourse
requestsadtonguewassat
cryingwhatbullyangry
Security Code: *
Include security image CAPCHA.
Refresh Code

® 2010-2026 GrowingScience.Com