Energy-Efficient Location-Routing Problem with Time Windows with Dynamic Demand
DOI:
https://doi.org/10.37266/ISER.2015v3i1.pp17-36Abstract
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
How to Cite
Issue
Section
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
The copyediting stage is intended to improve the flow, clarity, grammar, wording, and formatting of the article. It represents the last chance for the author to make any substantial changes to the text because the next stage is restricted to typos and formatting corrections. The file to be copyedited is in Word or .rtf format and therefore can easily be edited as a word processing document. The set of instructions displayed here proposes two approaches to copyediting. One is based on Microsoft Word's Track Changes feature and requires that the copy editor, editor, and author have access to this program. A second system, which is software independent, has been borrowed, with permission, from the Harvard Educational Review. The journal editor is in a position to modify these instructions, so suggestions can be made to improve the process for this journal.
