IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v271y2018i3p866-881.html
   My bibliography  Save this article

A Profit-Maximization Location-Routing-Pricing Problem: A Branch-and-Price Algorithm

Author

Listed:
  • Ahmadi-Javid, Amir
  • Amiri, Elahe
  • Meskar, Mahla

Abstract

This paper for the first time considers a profit-maximization location-routing problem with price-sensitive demands. The problem determines the location of facilities, the allocation of vehicles and customers to established facilities, and the pricing and routing decisions in order to maximize the total profit of serving customers. A mixed-integer linear programming model is presented, which can only be used to solve small-size instances with commercial optimization solvers. Then, the model is reformulated as a set-packing model and solved by an efficient branch-and-price algorithm for large-size instances. The proposed algorithm can also be used to solve the more basic problems such as location-routing with profit and price-inelastic demands or vehicle routing with profit and price-sensitive demands, which has not been considered by any research earlier. The column-generation procedure is developed based on a new variant of the elementary shortest path problem with resource constraints where demands are price dependent. Our numerical study indicates the substantial advantage of the integrated model. The proposed model can be used to design the distribution networks of online shopping systems in which delivered pricing is influenced by the last mile delivery.

Suggested Citation

  • Ahmadi-Javid, Amir & Amiri, Elahe & Meskar, Mahla, 2018. "A Profit-Maximization Location-Routing-Pricing Problem: A Branch-and-Price Algorithm," European Journal of Operational Research, Elsevier, vol. 271(3), pages 866-881.
    • Handle: RePEc:eee:ejores:v:271:y:2018:i:3:p:866-881
    DOI: 10.1016/j.ejor.2018.02.020
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221718301358
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2018.02.020?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Desrochers, Martin & Soumis, Francois, 1988. "A reoptimization algorithm for the shortest path problem with time windows," European Journal of Operational Research, Elsevier, vol. 35(2), pages 242-254, May.
    2. Salhi, Said & Rand, Graham K., 1989. "The effect of ignoring routes when locating depots," European Journal of Operational Research, Elsevier, vol. 39(2), pages 150-156, March.
    3. Greenhut, M L & Hwang, M & Ohta, H, 1975. "Observations on the Shape and Relevance of the Spatial Demand Function," Econometrica, Econometric Society, vol. 43(4), pages 669-682, July.
    4. He, Zhou & Cheng, T.C.E. & Dong, Jichang & Wang, Shouyang, 2016. "Evolutionary location and pricing strategies for service merchants in competitive O2O markets," European Journal of Operational Research, Elsevier, vol. 254(2), pages 595-609.
    5. Igor Averbakh & Oded Berman & David Simchi‐Levi, 1994. "Probabilistic a priori routing‐location problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 41(7), pages 973-989, December.
    6. Albareda-Sambola, Maria & Fernandez, Elena & Laporte, Gilbert, 2007. "Heuristic and lower bound for a stochastic location-routing problem," European Journal of Operational Research, Elsevier, vol. 179(3), pages 940-955, June.
    7. Ahmadi-Javid, Amir & Seddighi, Amir Hossein, 2013. "A location-routing problem with disruption risk," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 53(C), pages 63-82.
    8. Mina, Hokey & Jayaraman, Vaidyanathan & Srivastava, Rajesh, 1998. "Combined location-routing problems: A synthesis and future research directions," European Journal of Operational Research, Elsevier, vol. 108(1), pages 1-15, July.
    9. Igor Averbakh & Oded Berman, 1994. "Technical Note—Routing and Location-Routing p-Delivery Men Problems on a Path," Transportation Science, INFORMS, vol. 28(2), pages 162-166, May.
    10. Maria Paz Espinosa, 1992. "Delivered Pricing, FOB Pricing, and Collusion in Spatial Markets," RAND Journal of Economics, The RAND Corporation, vol. 23(1), pages 64-85, Spring.
    11. Anderson, Simon P & de Palma, Andre & Thisse, Jacques-Francois, 1989. "Spatial Price Policies Reconsidered," Journal of Industrial Economics, Wiley Blackwell, vol. 38(1), pages 1-18, September.
    12. C Archetti & D Feillet & A Hertz & M G Speranza, 2009. "The capacitated team orienteering and profitable tour problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(6), pages 831-842, June.
    13. Anja Lambrecht & Katja Seim & Naufel Vilcassim & Amar Cheema & Yuxin Chen & Gregory Crawford & Kartik Hosanagar & Raghuram Iyengar & Oded Koenigsberg & Robin Lee & Eugenio Miravete & Ozge Sahin, 2012. "Price discrimination in service industries," Marketing Letters, Springer, vol. 23(2), pages 423-438, June.
    14. Fackler, Paul L. & Goodwin, Barry K., 2001. "Spatial price analysis," Handbook of Agricultural Economics, in: B. L. Gardner & G. C. Rausser (ed.), Handbook of Agricultural Economics, edition 1, volume 1, chapter 17, pages 971-1024, Elsevier.
    15. Villeneuve, Daniel & Desaulniers, Guy, 2005. "The shortest path problem with forbidden paths," European Journal of Operational Research, Elsevier, vol. 165(1), pages 97-107, August.
    16. Hansen, Pierre & Thisse, Jacques-Francois & Hanjoul, Pierre, 1981. "Simple plant location under uniform delivered pricing," European Journal of Operational Research, Elsevier, vol. 6(2), pages 94-103, February.
    17. LEDERER, Philip J. & THISSE, Jacques-François, 1990. "Competitive location on networks under delivered pricing," LIDAM Reprints CORE 893, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    18. Pierre Hanjoul & Pierre Hansen & Dominique Peeters & Jacques-Francois Thisse, 1990. "Uncapacitated Plant Location Under Alternative Spatial Price Policies," Management Science, INFORMS, vol. 36(1), pages 41-57, January.
    19. Varian, Hal R., 1989. "Price discrimination," Handbook of Industrial Organization, in: R. Schmalensee & R. Willig (ed.), Handbook of Industrial Organization, edition 1, volume 1, chapter 10, pages 597-654, Elsevier.
    20. Igor Averbakh & Oded Berman, 2002. "Minmax p-Traveling Salesmen Location Problems on a Tree," Annals of Operations Research, Springer, vol. 110(1), pages 55-68, February.
    21. Tilk, Christian & Rothenbächer, Ann-Kathrin & Gschwind, Timo & Irnich, Stefan, 2017. "Asymmetry matters: Dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster," European Journal of Operational Research, Elsevier, vol. 261(2), pages 530-539.
    22. Igor Averbakh & Oded Berman, 1995. "Probabilistic Sales-Delivery Man and Sales-Delivery Facility Location Problems on a Tree," Transportation Science, INFORMS, vol. 29(2), pages 184-197, May.
    23. Fernandez, Pascual & Pelegrin, Blas & Garcia Perez, Maria Dolores & Peeters, Peter H., 2007. "A discrete long-term location-price problem under the assumption of discriminatory pricing: Formulations and parametric analysis," European Journal of Operational Research, Elsevier, vol. 179(3), pages 1050-1062, June.
    24. Nagy, Gabor & Salhi, Said, 2007. "Location-routing: Issues, models and methods," European Journal of Operational Research, Elsevier, vol. 177(2), pages 649-672, March.
    25. Carlton, Dennis W, 1983. "A Reexamination of Delivered Pricing Systems," Journal of Law and Economics, University of Chicago Press, vol. 26(1), pages 51-70, April.
    26. Archetti, Claudia & Bertazzi, Luca & Laganà, Demetrio & Vocaturo, Francesca, 2017. "The Undirected Capacitated General Routing Problem with Profits," European Journal of Operational Research, Elsevier, vol. 257(3), pages 822-833.
    27. Martin Desrochers & François Soumis, 1989. "A Column Generation Approach to the Urban Transit Crew Scheduling Problem," Transportation Science, INFORMS, vol. 23(1), pages 1-13, February.
    28. Drexl, Michael & Schneider, Michael, 2015. "A survey of variants and extensions of the location-routing problem," European Journal of Operational Research, Elsevier, vol. 241(2), pages 283-308.
    29. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    30. Jonathan Vogel, 2011. "Spatial Price Discrimination with Heterogeneous Firms," Journal of Industrial Economics, Wiley Blackwell, vol. 59(4), pages 661-676, December.
    31. Amiya Basu & Charles A. Ingene & Tridib Mazumdar, 2004. "The Pricing of Delivery Services," Journal of Regional Science, Wiley Blackwell, vol. 44(4), pages 743-772, November.
    32. Hansen, P. & Peeters, D. & Thisse, J.-F., 1997. "Facility location under zone pricing," LIDAM Reprints CORE 1251, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    33. Prodhon, Caroline & Prins, Christian, 2014. "A survey of recent research on location-routing problems," European Journal of Operational Research, Elsevier, vol. 238(1), pages 1-17.
    34. Stefan Irnich & Guy Desaulniers, 2005. "Shortest Path Problems with Resource Constraints," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 33-65, Springer.
    35. Dominique Feillet & Pierre Dejax & Michel Gendreau, 2005. "Traveling Salesman Problems with Profits," Transportation Science, INFORMS, vol. 39(2), pages 188-205, May.
    36. Gunawan, Aldy & Lau, Hoong Chuin & Vansteenwegen, Pieter, 2016. "Orienteering Problem: A survey of recent variants, solution approaches and applications," European Journal of Operational Research, Elsevier, vol. 255(2), pages 315-332.
    37. Margaretha Gansterer & Murat Küçüktepe & Richard F. Hartl, 2017. "The multi-vehicle profitable pickup and delivery problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(1), pages 303-319, January.
    38. Vansteenwegen, Pieter & Souffriau, Wouter & Oudheusden, Dirk Van, 2011. "The orienteering problem: A survey," European Journal of Operational Research, Elsevier, vol. 209(1), pages 1-10, February.
    39. Ahmadi Javid, Amir & Azad, Nader, 2010. "Incorporating location, routing and inventory decisions in supply chain network design," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(5), pages 582-597, September.
    40. Edgar M. Hoover, 1937. "Spatial Price Discrimination," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 4(3), pages 182-191.
    41. G. Nagy & S. Salhi, 1998. "The many-to-many location-routing problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 6(2), pages 261-275, December.
    42. Ahmadi-Javid, Amir & Hoseinpour, Pooya, 2015. "A location-inventory-pricing model in a supply chain distribution network with price-sensitive demands and inventory-capacity constraints," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 82(C), pages 238-255.
    43. Mamnoon Jamil & Rajan Batta & David M. Malon, 1994. "The Traveling Repairperson Home Base Location Problem," Transportation Science, INFORMS, vol. 28(2), pages 150-161, May.
    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. Afsar, Hasan Murat & Afsar, Sezin & Palacios, Juan José, 2021. "Vehicle routing problem with zone-based pricing," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    2. Vincent F. Yu & Grace Aloina & Hadi Susanto & Mohammad Khoirul Effendi & Shih-Wei Lin, 2022. "Regional Location Routing Problem for Waste Collection Using Hybrid Genetic Algorithm-Simulated Annealing," Mathematics, MDPI, vol. 10(12), pages 1-23, June.
    3. Seung Yoon Ko & Sung Won Cho & Chulung Lee, 2018. "Pricing and Collaboration in Last Mile Delivery Services," Sustainability, MDPI, vol. 10(12), pages 1-20, December.
    4. Li, Qiaoru & Wang, Yuanyuan & Li, Kun & Chen, Liang & Wei, Zhenlin, 2019. "Evolutionary dynamics of the last mile travel choice," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 536(C).
    5. Lihua Liu & Lai Soon Lee & Hsin-Vonn Seow & Chuei Yee Chen, 2022. "Logistics Center Location-Inventory-Routing Problem Optimization: A Systematic Review Using PRISMA Method," Sustainability, MDPI, vol. 14(23), pages 1-39, November.
    6. Ali Pedram & Shahryar Sorooshian & Freselam Mulubrhan & Afshin Abbaspour, 2023. "Incorporating Vehicle-Routing Problems into a Closed-Loop Supply Chain Network Using a Mixed-Integer Linear-Programming Model," Sustainability, MDPI, vol. 15(4), pages 1-24, February.
    7. Wang, Mengtong & Miao, Lixin & Zhang, Canrong, 2021. "A branch-and-price algorithm for a green location routing problem with multi-type charging infrastructure," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 156(C).
    8. Lin, Yun Hui & Tian, Qingyun, 2023. "Facility location and pricing problem: Discretized mill price and exact algorithms," European Journal of Operational Research, Elsevier, vol. 308(2), pages 568-580.

    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. Zhang, Ying & Qi, Mingyao & Lin, Wei-Hua & Miao, Lixin, 2015. "A metaheuristic approach to the reliable location routing problem under disruptions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 83(C), pages 90-110.
    2. Drexl, Michael & Schneider, Michael, 2015. "A survey of variants and extensions of the location-routing problem," European Journal of Operational Research, Elsevier, vol. 241(2), pages 283-308.
    3. Menezes, Mozart B.C. & Ruiz-Hernández, Diego & Verter, Vedat, 2016. "A rough-cut approach for evaluating location-routing decisions via approximation algorithms," Transportation Research Part B: Methodological, Elsevier, vol. 87(C), pages 89-106.
    4. Nagy, Gabor & Salhi, Said, 2007. "Location-routing: Issues, models and methods," European Journal of Operational Research, Elsevier, vol. 177(2), pages 649-672, March.
    5. Daniel Negrotto & Irene Loiseau, 2021. "A Branch & Cut algorithm for the prize-collecting capacitated location routing problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(1), pages 34-57, April.
    6. Ponboon, Sattrawut & Qureshi, Ali Gul & Taniguchi, Eiichi, 2016. "Branch-and-price algorithm for the location-routing problem with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 86(C), pages 1-19.
    7. Andrés Martínez-Reyes & Carlos L. Quintero-Araújo & Elyn L. Solano-Charris, 2021. "Supplying Personal Protective Equipment to Intensive Care Units during the COVID-19 Outbreak in Colombia. A Simheuristic Approach Based on the Location-Routing Problem," Sustainability, MDPI, vol. 13(14), pages 1-16, July.
    8. Orlis, Christos & Laganá, Demetrio & Dullaert, Wout & Vigo, Daniele, 2020. "Distribution with Quality of Service Considerations: The Capacitated Routing Problem with Profits and Service Level Requirements," Omega, Elsevier, vol. 93(C).
    9. Janjevic, Milena & Winkenbach, Matthias & Merchán, Daniel, 2019. "Integrating collection-and-delivery points in the strategic design of urban last-mile e-commerce distribution networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 131(C), pages 37-67.
    10. Moshe Mann & Boaz Zion & Dror Rubinstein & Rafi Linker & Itzhak Shmulevich, 2016. "The Orienteering Problem with Time Windows Applied to Robotic Melon Harvesting," Journal of Optimization Theory and Applications, Springer, vol. 168(1), pages 246-267, January.
    11. Zhu, Stuart X. & Ursavas, Evrim, 2018. "Design and analysis of a satellite network with direct delivery in the pharmaceutical industry," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 116(C), pages 190-207.
    12. Hunkar Toyoglu & Oya Ekin Karasan & Bahar Yetis Kara, 2011. "Distribution network design on the battlefield," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(3), pages 188-209, April.
    13. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    14. Bergmann, Felix M. & Wagner, Stephan M. & Winkenbach, Matthias, 2020. "Integrating first-mile pickup and last-mile delivery on shared vehicle routes for efficient urban e-commerce distribution," Transportation Research Part B: Methodological, Elsevier, vol. 131(C), pages 26-62.
    15. Younes Rahmani & Wahiba Ramdane Cherif-Khettaf & Ammar Oulamara, 2016. "The two-echelon multi-products location-routing problem with pickup and delivery: formulation and heuristic approaches," International Journal of Production Research, Taylor & Francis Journals, vol. 54(4), pages 999-1019, February.
    16. Janjevic, Milena & Merchán, Daniel & Winkenbach, Matthias, 2021. "Designing multi-tier, multi-service-level, and multi-modal last-mile distribution networks for omni-channel operations," European Journal of Operational Research, Elsevier, vol. 294(3), pages 1059-1077.
    17. Ben Mohamed, Imen & Klibi, Walid & Sadykov, Ruslan & Şen, Halil & Vanderbeck, François, 2023. "The two-echelon stochastic multi-period capacitated location-routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 645-667.
    18. Michael Schneider & Michael Drexl, 2017. "A survey of the standard location-routing problem," Annals of Operations Research, Springer, vol. 259(1), pages 389-414, December.
    19. Afsar, Hasan Murat & Afsar, Sezin & Palacios, Juan José, 2021. "Vehicle routing problem with zone-based pricing," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    20. Arslan, Okan, 2021. "The location-or-routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 147(C), pages 1-21.

    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:eee:ejores:v:271:y:2018:i:3:p:866-881. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.