Energy-Efficient Location-Routing Problem with Time Windows with Dynamic Demand

  • Shokoufeh Mirzaei
  • Krishna Krishnan
  • Bayram Yildrim

Abstract

Sustainability and energy savings have attracted considerable attention in recent years. However, in the traditional location-routing problem (LRP), the objective function has yet to minimize the distance traveled regardless of the amount of energy consumed. Although, distance is one of the major factors determining the energy consumption of a distribution network, it is not the only factor. Therefore, this paper explains the development of a novel formulation of the LRP that considers energy minimization, which is called the energy-efficient location-routing problem (EELRP). The energy consumed by a vehicle to travel between two nodes in a system depends on many forces. Among those, rolling resistance (RR) and aerodynamic drag are considered in this paper to be the major contributing forces. The presented mixed-integer non-linear program (MINLP) finds the best location-allocation routing plan with the objective function of minimizing total costs, including energy, emissions, and depot establishment. The proposed model can also handle the vehicle-selection problem with respect to a vehicles’ capacity, source of energy, and aerodynamic characteristics. The formulation proposed can also solve the problems with hard and soft time window constraints. Also, the model is enhanced to handle the EELRP with dynamic customers’ demands. Some examples are presented to illustrate the formulations presented in this paper.

References

Artmeier, A., Haselmayr, J., Leucker, M., and Sachenbacher, M. (2010a). The optimal routing problem in the context of battery-powered electric vehicles, Workshop: CROCS at CPAIOR-10, Second International Workshop on Constraint Reasoning and Optimization for Computational Sustainability, Bologna, Italy, 2010.

Artmeier, A., Haselmayr, J., Leucker, M., and Sachenbacher, M. (2010b). The shortest path problem revisited: Optimal routing for electric vehicles. KI 2010: Advances in Artificial Intelligence, 309-316.

Bard, J., Kontoravdis, G., and Yu, G. (2002). A branch-and-cut procedure for the vehicle routing problem with time windows. Transportation Science, 36(2), 250.

Braysy, O. and Gendreau, M. (2005a). Vehicle routing problem with time windows. Part I: Route construction and local search algorithms. Transportation Science, 39(1), 104-118.

Braysy, O. and Gendreau, M. (2005b). Vehicle routing problem with time windows. Part II: Metaheuristics. Transportation Science, 39(1), 119-139.

Chabrier, A. (2006). Vehicle routing problem with elementary shortest path based column generation. Computers and Operations Research, 33(10), 2972-2990.

Cook, W. and Rich, J. (1999). A parallel cutting-plane algorithm for the vehicle routing problem with time windows. Technical Report, Computational and Applied Mathematics, Rice University, Houston, 5

Danna, E. and Pape, C. (2005). Branch-and-price heuristics: A case study on the vehicle routing problem with time windows. In Column Generation, Desaulniers, G., Desrosiers, J., and Solomon M.M. (eds.), 99-129. Springer, Berlin.

Dantzig, G., Fulkerson, R., and Johnson, S. (1954). Solution of a large-scale traveling-salesman problem. Journal of the Operations Research Society of America, 2(4), 393-410.

Desrochers, M., Lenstra, J., Savelsbergh, M., and Soumis, F. (1987). Vehicle routing with time windows: Optimization and approximation. Department of Operations Research and System Theory, Centrum voor Wiskunde en Informatica.

Desrochers, M., Desrosiers, J., and Solomon, M. (1992). A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 40(2), 342-354.

Eksioglu, B., Vural, A., and Reisman, A. (2009). The vehicle routing problem: A taxonomic review, Computers and Industrial Engineering, 57(4), 1472-1483.

Feillet, D., Dejax, P., Gendreau, M., and Gueguen, C. (2004). An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks, 44(3), 216-229.

Fisher, M., Jörnsten, K., and Madsen, O. (1997), Vehicle routing with time windows: Two optimization algorithms. Operations Research, 45(3), 488-492.

Gusikhin, O., MacNeille, P., and Cohn, A. (2010). Vehicle routing to minimize mixed-fleet fuel consumption and environmental impact. Proceeding of International Conference on Informatics in Controls, 7.

Halse, K. (1992). Modeling and solving complex vehicle routing problems. Ph.D. Dissertation. IMSOR, The Technical University of Denmark, Lyngby, Denmark.

Held, M. and Karp, R. (1970). The traveling-salesman problem and minimum spanning trees: Part I. Operations Research, 18, 1138-1162.

Held, M. and Karp, R. (1971). The traveling-salesman problem and minimum spanning trees: Part II. Mathematical Programming, 1(1), 6-25.

Hirashima, K., Furuya, H., and Kawashima, H. (2002). The study of vehicle routing problem considering car gas emission. Infrastructure Planning Review, 19(2), 275-282.

Houck, D. (1978). The traveling salesman problem as a constrained shortest path problem: Theory and computational experience. Ecole polytechnique de Montréal, 1978 – 62.

Kallehauge, B., Boland, N., and Madsen, O. (2007). Path inequalities for the vehicle routing problem with time windows. Networks, 49(4), 273-293.

Kallehauge, B. (2008). Formulations and exact algorithms for the vehicle routing problem with time windows. Computers and Operations Research, 35(7), 2307-2330.

Kolen, A., Kan, A., and Trienekens, H. (1987). Vehicle routing with time windows. Operations Research, 35(2), 266-273.

Kohl, N. and Madsen, O. (1997). An optimization algorithm for the vehicle routing problem with time windows based on lagrangian relaxation. Operations Research, 45(3), 395-406.

Kara, I., Kara, B., and Yetis, M. (2007). Energy minimizing vehicle routing problem. Combinatorial Optimization and Applications, 4616/2007, 62-71.

Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345-358.

Laporte, G., Nobert, Y., and Taillefer, S. (1988). Solving a family of multi-depot vehicle routing and location-routing problems. Transportation Science, 22(3), 161-172.

Laporte, G., Gendreau, M., Potvin, J., and Semet, F. (2000). Classical and modern heuristics for the vehicle routing problem. International Transactions in Operational Research, 7(4-5), 285-300.

Larsen, J. (1999). Parallelization of the vehicle routing problem with time windows. Institute of Mathematical Modelling, Technical University of Denmark.

Larsen, J. (2004). Refinements of the column generation process for the vehicle routing problem with time windows. Journal of Systems Science and Systems Engineering, 13(3), 326-341.

Mak, V. and Ernst, A. (2007). New cutting-planes for the time-and/or precedence-constrained ATSP and directed VRP. Mathematical Methods of Operations Research, 66(1), 69-98.

Miller, C., Tucker, A., and Zemlin, R. (1960). Integer programming formulation of traveling salesman problems. Journal of the ACM (JACM), 7(4), 329.

Mirzaei, S. and Krishnan, K.K. (2011). Supply chain network configuration with time dependent demand, Proceedings of the Industrial Engineering Research Conference 2011, Reno, Nevada.

Published
2015-01-21
How to Cite
Mirzaei, S., Krishnan, K., & Yildrim, B. (2015). Energy-Efficient Location-Routing Problem with Time Windows with Dynamic Demand. Industrial and Systems Engineering Review, 3(1), 17-36. Retrieved from http://watsonojs.binghamton.edu/index.php/iser/article/view/31