Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

The green vehicle routing problem with capacitated alternative fuel stations

Published: 01 December 2019 Publication History

Highlights

Introduction of the station capacity in the Green Vehicle Routing Problem.
Reservation of the fueling pumps and time windows associated with them.
Arc based and Path based Mixed Integer Programming formulations.
Two variants of an exact cutting planes approach to speed up the models.
Generation of a benchmark set of challenging instances for the new problem.

Abstract

In this paper, we introduce the Green Vehicle Routing Problem with capacitated Alternative Fuel Stations (AFSs), a more realistic variant of the Green Vehicle Routing Problem where the capacity of the AFSs is addressed. Two Mixed Integer Linear Programming formulations, one based on arc-variables and one on path-variables are presented. In order to reduce the computational time required to solve the problem, two variants of an exact cutting planes method are proposed. All the proposed approaches are also extended to be applied in a scenario in which AFSs reservation is allowed, by introducing time windows at them. Computational experiments are carried out on both benchmark and challenging realistic instances for which the capacity of the AFSs is a crucial issue.

References

[1]
M. Affi, H. Derbel, B. Jarboui, Variable neighborhood search algorithm for the green vehicle routing problem, Int. J. Ind. Eng. Comput. 9 (2) (2018) 195–204.
[2]
J. Andelmin, E. Bartolini, An exact algorithm for the green vehicle routing problem, Trans. Sci. 51 (4) (2017) 1288–1303.
[3]
J. Andelmin, E. Bartolini, A multi-start local search heuristic for the green vehicle routing problem based on a multigraph reformulation, Comput. Oper. Res. 109 (2019) 43–63.
[4]
J.F. Bard, L. Huang, M. Dror, P. Jaillet, A branch and cut algorithm for the VRP with satellite facilities, IIE Trans. 30 (9) (1998) 821–834.
[5]
T. Bektaş, E. Demir, G. Laporte, Green vehicle routing, Green Transportation Logistics, Springer, 2016, pp. 243–265.
[6]
M. Bruglieri, S. Mancini, F. Pezzella, O. Pisacane, A new mathematical programming model for the green vehicle routing problem, Electron. Note. Discrete Math. 55 (2016) 89–92.
[7]
M. Bruglieri, S. Mancini, F. Pezzella, O. Pisacane, A path-based solution approach for the green vehicle routing problem, Comput. Oper. Res. 103 (2019) 109–122.
[8]
M. Bruglieri, S. Mancini, F. Pezzella, O. Pisacane, S. Suraci, A three-phase matheuristic for the time-effective electric vehicle routing problem with partial recharges, Electron. Note. Discrete Math. 58 (2017) 95–102.
[9]
M. Bruglieri, S. Mancini, O. Pisacane, Solving the green vehicle routing problem with capacitated alternative fuel stations, Proceedings of 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Paris, France, 2018, pp. 196–199.
[10]
M. Bruglieri, F. Pezzella, O. Pisacane, S. Suraci, A variable neighborhood search branching for the electric vehicle routing problem with time windows, Electron. Note. Discrete Math. 47 (2015) 221–228.
[11]
E. Demir, T. Bektaş, G. Laporte, A review of recent research on green road freight transportation, Eur. J. Oper. Res. 237 (3) (2014) 775–793.
[12]
G. Desaulniers, F. Errico, S. Irnich, M. Schneider, Exact algorithms for electric vehicle-routing problems with time windows, Oper. Res. 64 (6) (2016) 1388–1405.
[13]
S. Erdoğan, E. Miller-Hooks, A green vehicle routing problem, Transp. Res. Part E 48 (1) (2012) 100–114.
[14]
Á. Felipe, M.T. Ortuño, G. Righini, G. Tirado, A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges, Transp. Res. Part E 71 (2014) 111–128.
[15]
W. Feng, M.A. Figliozzi, Conventional vs electric commercial vehicle fleets: a case study of economic and technological factors affecting the competitiveness of electric commercial vehicles in the usa, Procedia-Soc. Behav. Sci. 39 (2012) 702–711.
[16]
T. Gnann, S. Funke, N. Jakobsson, P. Plötz, F. Sprei, A. Bennehag, Fast charging infrastructure for electric vehicles: todayâs situation and future needs, Transp. Res. Part D 62 (2018) 314–329.
[17]
G. Hiermann, R.F. Hartl, J. Puchinger, T. Vidal, Routing a mix of conventional, plug-in hybrid, and electric vehicles, Eur. J. Oper. Res. 272 (1) (2019) 235–248.
[18]
G. Hiermann, J. Puchinger, S. Ropke, R.F. Hartl, The electric fleet size and mix vehicle routing problem with time windows and recharging stations, Eur. J. Oper. Res. 252 (3) (2016) 995–1018.
[19]
Y.-C. Hung, G. Michailidis, Optimal routing for electric vehicle service systems, Eur. J. Oper. Res. 247 (2) (2015) 515–524.
[20]
J. Jemai, M. Zekri, K. Mellouli, An NSGA-II algorithm for the green vehicle routing problem, European Conference on Evolutionary Computation in Combinatorial Optimization, Springer, 2012, pp. 37–48.
[21]
A.D. Jovanović, D.S. Pamučar, S. Pejčić-Tarle, Green vehicle routing in urban zones–a neuro-fuzzy approach, Expert Syst. Appl. 41 (7) (2014) 3189–3203.
[22]
C.D. Keeling, S.C. Piper, R.B. Bacastow, M. Wahlen, T.P. Whorf, M. Heimann, H.A. Meijer, Exchanges of atmospheric CO2 and 13CO2 with the terrestrial biosphere and oceans from 1978 to 2000. I. global aspects, Scripps Institution of Oceanography, UC San Diego, 2001.
[23]
C.D. Keeling, S.C. Piper, R.B. Bacastow, M. Wahlen, T.P. Whorf, M. Heimann, H.A. Meijer, Atmospheric co 2 and 13 co 2 exchange with the terrestrial biosphere and oceans from 1978 to 2000: observations and carbon cycle implications, A history of atmospheric CO2 and its effects on plants, animals, and ecosystems, Springer, 2005, pp. 83–113.
[24]
M. Keskin, G. Laporte, B. Çatay, Electric vehicle routing problem with time-dependent waiting times at recharging stations, Comput. Oper. Res. 107 (2019) 77–94.
[25]
Ç. Koç, I. Karaoglan, The green vehicle routing problem: a heuristic based exact solution approach, Appl. Soft Comput. 39 (2016) 154–164.
[26]
G. Laporte, Y. Nobert, A cutting planes algorithm for the m-salesmen problem, J. Oper. Res. Soc. 31 (11) (1980) 1017–1023.
[27]
V. Leggieri, M. Haouari, A practical solution approach for the green vehicle routing problem, Transp. Res. Part E 104 (2017) 97–112.
[28]
C. Lin, K.L. Choy, G.T. Ho, S.H. Chung, H. Lam, Survey of green vehicle routing problem: past and future trends, Expert Syst. Appl. 41 (4) (2014) 1118–1138.
[29]
S. Majidi, S.-M. Hosseini-Motlagh, S. Yaghoubi, A. Jokar, Fuzzy green vehicle routing problem with simultaneous pickup–delivery and time windows, RAIRO-Oper. Res. 51 (4) (2017) 1151–1176.
[30]
S. Mancini, The hybrid vehicle routing problem, Transp. Res. Part C 78 (2017) 1–12.
[31]
H. Marchand, A. Martin, R. Weismantel, L. Wolsey, Cutting planes in integer and mixed integer programming, Discrete Appl. Math. 123 (2002) 397–446.
[32]
A. Montoya, C. Guéret, J.E. Mendoza, J.G. Villegas, A multi-space sampling heuristic for the green vehicle routing problem, Transp. Res. Part C 70 (2016) 113–128.
[33]
A. Montoya, C. Guéret, J.E. Mendoza, J.G. Villegas, The electric vehicle routing problem with nonlinear charging function, Transp. Res. Part B 103 (2017) 87–110.
[34]
B. Sawik, J. Faulin, E. Pérez-Bernabeu, Multi-criteria optimization for fleet size with environmental aspects, Transp. Res. Procedia 27 (2017) 61–68.
[35]
B. Sawik, J. Faulin, E. Pérez-Bernabeu, A multicriteria analysis for the green VRP: a case discussion for the distribution problem of a spanish retailer, Transp. Res. Procedia 22 (2017) 305–313.
[36]
M. Schneider, A. Stenger, D. Goeke, The electric vehicle-routing problem with time windows and recharging stations, Transp. Sci. 48 (4) (2014) 500–520.
[37]
M. Schneider, A. Stenger, J. Hof, An adaptive VNS algorithm for vehicle routing problems with intermediate stops, OR Spectrum 37 (2) (2015) 353–387.
[38]
L. Wang, J. Lu, A memetic algorithm with competition for the capacitated green vehicle routing problem, IEEE/CAA J. Automat. Sinica 6 (2) (2019) 516–526.
[39]
A. Zhang, J.E. Kang, C. Kwon, Incorporating demand dynamics in multi-period capacitated fast-charging location planning for electric vehicles, Transp. Res. Part B 103 (2017) 5–29.
[40]
S. Zhang, Y. Gajpal, S. Appadoo, A meta-heuristic for capacitated green vehicle routing problem, Annal. Oper. Res. 269 (1–2) (2018) 753–771.

Index Terms

  1. The green vehicle routing problem with capacitated alternative fuel stations
    Index terms have been assigned to the content through auto-classification.

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image Computers and Operations Research
    Computers and Operations Research  Volume 112, Issue C
    Dec 2019
    271 pages

    Publisher

    Elsevier Science Ltd.

    United Kingdom

    Publication History

    Published: 01 December 2019

    Author Tags

    1. Vehicle routing problem
    2. Alternative fuel vehicles
    3. Mixed integer linear programming
    4. Cutting planes
    5. Fueling pump reservation

    Qualifiers

    • Research-article

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • 0
      Total Citations
    • 0
      Total Downloads
    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 29 Nov 2024

    Other Metrics

    Citations

    View Options

    View options

    Login options

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media