IDEAS home Printed from https://ideas.repec.org/a/gam/jsusta/v10y2018i11p4257-d183629.html
   My bibliography  Save this article

A Bi-Objective Vehicle-Routing Problem with Soft Time Windows and Multiple Depots to Minimize the Total Energy Consumption and Customer Dissatisfaction

Author

Listed:
  • Shijin Wang

    (Department of Management Science & Engineering, School of Economics & Management, Tongji University, Shanghai 710049, China)

  • Xiaodong Wang

    (Department of Management Science & Engineering, School of Economics & Management, Tongji University, Shanghai 710049, China)

  • Xin Liu

    (Department of Management Science & Engineering, School of Economics & Management, Tongji University, Shanghai 710049, China)

  • Jianbo Yu

    (School of Mechanical Engineering, Tongji University, Shanghai 201804, China)

Abstract

In recent years, the impact of the energy crisis and environment pollution on quality of life has forced industry to actively participate in the development of a sustainable society. Simultaneously, customer satisfaction improvement has always been a goal of businesses. It is recognized that efficient technologies and advanced methods can help transportation companies find a better balance between progress in energy saving and customer satisfaction. This paper investigates a bi-objective vehicle-routing problem with soft time windows and multiple depots, which aims to simultaneously minimize total energy consumption and customer dissatisfaction. To address the problem, we first develop mixed-integer programming. Then, an augmented ϵ -constraint method is adopted to obtain the optimal Pareto front for small problems. It is very time consuming for the augmented ϵ -constraint method to precisely solve even medium-sized problems. For medium- and large-sized problems, two Non-dominated Sorting Genetic Algorithm-II (NSGA-II)-based heuristics with different rules for generating initial solutions and offspring are designed. The performance of the proposed methods is evaluated by 100 randomly generated instances. Computational results show that the second NSGA-II-based heuristic is highly effective in finding approximate non-dominated solutions for small-size and medium-size instances, and the first one is performs better for the large-size instances.

Suggested Citation

  • Shijin Wang & Xiaodong Wang & Xin Liu & Jianbo Yu, 2018. "A Bi-Objective Vehicle-Routing Problem with Soft Time Windows and Multiple Depots to Minimize the Total Energy Consumption and Customer Dissatisfaction," Sustainability, MDPI, vol. 10(11), pages 1-21, November.
    • Handle: RePEc:gam:jsusta:v:10:y:2018:i:11:p:4257-:d:183629
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2071-1050/10/11/4257/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2071-1050/10/11/4257/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Bérubé, Jean-François & Gendreau, Michel & Potvin, Jean-Yves, 2009. "An exact [epsilon]-constraint method for bi-objective combinatorial optimization problems: Application to the Traveling Salesman Problem with Profits," European Journal of Operational Research, Elsevier, vol. 194(1), pages 39-50, April.
    2. Gerardo Berbeglia & Jean-François Cordeau & Irina Gribkovskaia & Gilbert Laporte, 2007. "Rejoinder on: Static pickup and delivery problems: a classification scheme and survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 15(1), pages 45-47, July.
    3. Bektas, Tolga & Laporte, Gilbert, 2011. "The Pollution-Routing Problem," Transportation Research Part B: Methodological, Elsevier, vol. 45(8), pages 1232-1250, September.
    4. Francis, Peter & Smilowitz, Karen, 2006. "Modeling techniques for periodic vehicle routing problems," Transportation Research Part B: Methodological, Elsevier, vol. 40(10), pages 872-884, December.
    5. Gulczynski, Damon & Golden, Bruce & Wasil, Edward, 2011. "The period vehicle routing problem: New heuristics and real-world variants," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 47(5), pages 648-668, September.
    6. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms," Transportation Science, INFORMS, vol. 39(1), pages 104-118, February.
    7. Erdoğan, Sevgi & Miller-Hooks, Elise, 2012. "A Green Vehicle Routing Problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 100-114.
    8. Guy Desaulniers & Fausto Errico & Stefan Irnich & Michael Schneider, 2016. "Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows," Operations Research, INFORMS, vol. 64(6), pages 1388-1405, December.
    9. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation Science, INFORMS, vol. 39(1), pages 119-139, February.
    10. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    11. Demir, Emrah & Bektaş, Tolga & Laporte, Gilbert, 2014. "The bi-objective Pollution-Routing Problem," European Journal of Operational Research, Elsevier, vol. 232(3), pages 464-478.
    12. Tan, K.C. & Chew, Y.H. & Lee, L.H., 2006. "A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 172(3), pages 855-885, August.
    13. Gilbert Laporte, 2009. "Fifty Years of Vehicle Routing," Transportation Science, INFORMS, vol. 43(4), pages 408-416, November.
    14. Liu, Ming & Lee, Chung-Yee & Zhang, Zizhen & Chu, Chengbin, 2016. "Bi-objective optimization for the container terminal integrated planning," Transportation Research Part B: Methodological, Elsevier, vol. 93(PB), pages 720-749.
    15. Salani, Matteo & Vacca, Ilaria, 2011. "Branch and price for the vehicle routing problem with discrete split deliveries and time windows," European Journal of Operational Research, Elsevier, vol. 213(3), pages 470-477, September.
    16. Gilbert Laporte, 2007. "What you should know about the vehicle routing problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(8), pages 811-819, December.
    17. Gerardo Berbeglia & Jean-François Cordeau & Irina Gribkovskaia & Gilbert Laporte, 2007. "Static pickup and delivery problems: a classification scheme and survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 15(1), pages 1-31, July.
    18. M. Ehrgott & S. Ruzika, 2008. "Improved ε-Constraint Method for Multiobjective Programming," Journal of Optimization Theory and Applications, Springer, vol. 138(3), pages 375-396, September.
    19. Wan-Yu Liu & Chun-Cheng Lin & Ching-Ren Chiu & You-Song Tsao & Qunwei Wang, 2014. "Minimizing the Carbon Footprint for the Time-Dependent Heterogeneous-Fleet Vehicle Routing Problem with Alternative Paths," Sustainability, MDPI, vol. 6(7), pages 1-27, July.
    20. Dondo, Rodolfo & Cerda, Jaime, 2007. "A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1478-1507, February.
    21. Goel, Asvin & Gruhn, Volker, 2008. "A General Vehicle Routing Problem," European Journal of Operational Research, Elsevier, vol. 191(3), pages 650-660, December.
    22. J-F Cordeau & G Laporte & A Mercier, 2001. "A unified tabu search heuristic for vehicle routing problems with time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(8), pages 928-936, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Qiuchi Xue & Xin Yang & Jianjun Wu & Huijun Sun & Haodong Yin & Yunchao Qu, 2019. "Urban Rail Timetable Optimization to Improve Operational Efficiency with Flexible Routing Plans: A Nonlinear Integer Programming Model," Sustainability, MDPI, vol. 11(13), pages 1-26, July.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Lahyani, Rahma & Khemakhem, Mahdi & Semet, Frédéric, 2015. "Rich vehicle routing problems: From a taxonomy to a definition," European Journal of Operational Research, Elsevier, vol. 241(1), pages 1-14.
    2. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    3. Schmid, Verena & Doerner, Karl F. & Laporte, Gilbert, 2013. "Rich routing problems arising in supply chain management," European Journal of Operational Research, Elsevier, vol. 224(3), pages 435-448.
    4. Liu, Yiming & Roberto, Baldacci & Zhou, Jianwen & Yu, Yang & Zhang, Yu & Sun, Wei, 2023. "Efficient feasibility checks and an adaptive large neighborhood search algorithm for the time-dependent green vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 310(1), pages 133-155.
    5. Wang, Zheng, 2018. "Delivering meals for multiple suppliers: Exclusive or sharing logistics service," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 496-512.
    6. Schneider, Michael, 2016. "The vehicle-routing problem with time windows and driver-specific times," European Journal of Operational Research, Elsevier, vol. 250(1), pages 101-119.
    7. Pureza, Vitória & Morabito, Reinaldo & Reimann, Marc, 2012. "Vehicle routing with multiple deliverymen: Modeling and heuristic approaches for the VRPTW," European Journal of Operational Research, Elsevier, vol. 218(3), pages 636-647.
    8. Baals, Julian & Emde, Simon & Turkensteen, Marcel, 2023. "Minimizing earliness-tardiness costs in supplier networks—A just-in-time truck routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 707-741.
    9. Raeesi, Ramin & Zografos, Konstantinos G., 2020. "The electric vehicle routing problem with time windows and synchronised mobile battery swapping," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 101-129.
    10. Mohammad Torkjazi & Nathan Huynh, 2019. "Effectiveness of Dynamic Insertion Scheduling Strategy for Demand-Responsive Paratransit Vehicles Using Agent-Based Simulation," Sustainability, MDPI, vol. 11(19), pages 1-12, September.
    11. Zajac, Sandra & Huber, Sandra, 2021. "Objectives and methods in multi-objective routing problems: a survey and classification scheme," European Journal of Operational Research, Elsevier, vol. 290(1), pages 1-25.
    12. Bhusiri, Narath & Qureshi, Ali Gul & Taniguchi, Eiichi, 2014. "The trade-off between fixed vehicle costs and time-dependent arrival penalties in a routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 62(C), pages 1-22.
    13. Goeke, Dominik & Schneider, Michael, 2015. "Routing a mixed fleet of electric and conventional vehicles," European Journal of Operational Research, Elsevier, vol. 245(1), pages 81-99.
    14. Mohamed Cissé & Semih Yalçindag & Yannick Kergosien & Evren Sahin & Christophe Lenté & Andrea Matta, 2017. "OR problems related to Home Health Care: A review of relevant routing and scheduling problems," Post-Print hal-01736714, HAL.
    15. Schneider, Michael & Schwahn, Fabian & Vigo, Daniele, 2017. "Designing granular solution methods for routing problems with time windows," European Journal of Operational Research, Elsevier, vol. 263(2), pages 493-509.
    16. Michael Schneider & Andreas Stenger & Dominik Goeke, 2014. "The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations," Transportation Science, INFORMS, vol. 48(4), pages 500-520, November.
    17. Goeke, D. & Schneider, M., 2015. "Routing a Mixed Fleet of Electric and Conventional Vehicles," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 65939, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    18. Hiermann, Gerhard & Puchinger, Jakob & Ropke, Stefan & Hartl, Richard F., 2016. "The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations," European Journal of Operational Research, Elsevier, vol. 252(3), pages 995-1018.
    19. Qiuping Ni & Yuanxiang Tang, 2023. "A Bibliometric Visualized Analysis and Classification of Vehicle Routing Problem Research," Sustainability, MDPI, vol. 15(9), pages 1-37, April.
    20. Liu, Ran & Xie, Xiaolan & Garaix, Thierry, 2014. "Hybridization of tabu search with feasible and infeasible local searches for periodic home health care logistics," Omega, Elsevier, vol. 47(C), pages 17-32.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jsusta:v:10:y:2018:i:11:p:4257-:d:183629. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.