IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v41y2007i3p302-318.html
   My bibliography  Save this article

Pricing in Dynamic Vehicle Routing Problems

Author

Listed:
  • Miguel Andres Figliozzi

    (Faculty of Economics and Business, Institute of Transport and Logistics Studies, University of Sydney, Sydney, NSW 2006, Australia)

  • Hani S. Mahmassani

    (Department of Civil and Environmental Engineering, Martin Hall, University of Maryland, College Park, College Park, Maryland 20742)

  • Patrick Jaillet

    (Department of Civil and Environmental Engineering, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139-4307)

Abstract

The principal focus of this paper is to study carrier pricing decisions for a type of vehicle routing problems defined in a competitive and dynamic environment. This paper introduces the vehicle routing problem in a competitive environment (VRPCE) as an extension of the traveling-salesman problem with profits (TSPP) to a dynamic competitive auction environment. In the VRPCE, the carrier must estimate the incremental cost of servicing new service requests as they arrive dynamically. The paper presents a rigorous and precise treatment of the sequential pricing and costing problem that a carrier faces in such an environment. The sequential pricing problem presented here is an intrinsic feature of a sequential auction problem. In addition to introducing the formulation of this class of problems and discussing the main sources of difficulty in devising a solution, a simple example is constructed to show that carriers’ prices under first-price auction payment rules do not necessarily reflect the cost of servicing transportation requests. An approximate solution approach with a finite rolling horizon is presented and illustrated through numerical experiments, in competition with a static approach with no look-ahead.

Suggested Citation

  • Miguel Andres Figliozzi & Hani S. Mahmassani & Patrick Jaillet, 2007. "Pricing in Dynamic Vehicle Routing Problems," Transportation Science, INFORMS, vol. 41(3), pages 302-318, August.
    • Handle: RePEc:inm:ortrsc:v:41:y:2007:i:3:p:302-318
    DOI: 10.1287/trsc.1070.0193
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1070.0193
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1070.0193?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
    ---><---

    References listed on IDEAS

    as
    1. Gendreau, Michel & Laporte, Gilbert & Seguin, Rene, 1996. "Stochastic vehicle routing," European Journal of Operational Research, Elsevier, vol. 88(1), pages 3-12, January.
    2. Gilbert Laporte & François Louveaux & Hélène Mercure, 1992. "The Vehicle Routing Problem with Stochastic Travel Times," Transportation Science, INFORMS, vol. 26(3), pages 161-170, August.
    3. Mitrovic-Minic, Snezana & Krishnamurti, Ramesh & Laporte, Gilbert, 2004. "Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 38(8), pages 669-685, September.
    4. Dimitris J. Bertsimas & Patrick Jaillet & Amedeo R. Odoni, 1990. "A Priori Optimization," Operations Research, INFORMS, vol. 38(6), pages 1019-1033, December.
    5. Mitrovic-Minic, Snezana & Laporte, Gilbert, 2004. "Waiting strategies for the dynamic pickup and delivery problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 38(7), pages 635-655, August.
    6. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    7. Bruce L. Golden & Larry Levy & Rakesh Vohra, 1987. "The orienteering problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 34(3), pages 307-318, June.
    8. Marius M. Solomon & Jacques Desrosiers, 1988. "Survey Paper---Time Window Constrained Routing and Scheduling Problems," Transportation Science, INFORMS, vol. 22(1), pages 1-13, February.
    9. Russell W. Bent & Pascal Van Hentenryck, 2004. "Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers," Operations Research, INFORMS, vol. 52(6), pages 977-987, December.
    10. Jürgen Branke & Martin Middendorf & Guntram Noeth & Maged Dessouky, 2005. "Waiting Strategies for Dynamic Vehicle Routing," Transportation Science, INFORMS, vol. 39(3), pages 298-312, August.
    11. Warren B. Powell & Michael T. Towns & Arun Marar, 2000. "On the Value of Optimal Myopic Solutions for Dynamic Routing and Scheduling Problems in the Presence of User Noncompliance," Transportation Science, INFORMS, vol. 34(1), pages 67-85, February.
    12. Song, Jiongjiong & Regan, Amelia, 2005. "Approximation algorithms for the bid construction problem in combinatorial auctions for the procurement of freight transportation contracts," Transportation Research Part B: Methodological, Elsevier, vol. 39(10), pages 914-933, December.
    13. Anton J. Kleywegt & Jason D. Papastavrou, 1998. "Acceptance and Dispatching Policies for a Distribution Problem," Transportation Science, INFORMS, vol. 32(2), pages 127-141, May.
    14. Patrick Jaillet, 1988. "A Priori Solution of a Traveling Salesman Problem in Which a Random Subset of the Customers Are Visited," Operations Research, INFORMS, vol. 36(6), pages 929-936, December.
    15. Warren B. Powell, 1986. "A Stochastic Model of the Dynamic Vehicle Allocation Problem," Transportation Science, INFORMS, vol. 20(2), pages 117-129, May.
    16. Soumia Ichoua & Michel Gendreau & Jean-Yves Potvin, 2006. "Exploiting Knowledge About Future Demands for Real-Time Vehicle Dispatching," Transportation Science, INFORMS, vol. 40(2), pages 211-225, May.
    17. Powell, Warren B., 1987. "An operational planning model for the dynamic vehicle allocation problem with uncertain demands," Transportation Research Part B: Methodological, Elsevier, vol. 21(3), pages 217-232, June.
    18. Gregory A. Godfrey & Warren B. Powell, 2002. "An Adaptive Dynamic Programming Algorithm for Dynamic Fleet Management, I: Single Period Travel Times," Transportation Science, INFORMS, vol. 36(1), pages 21-39, February.
    19. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    20. Yossi Sheffi, 2004. "Combinatorial Auctions in the Procurement of Transportation Services," Interfaces, INFORMS, vol. 34(4), pages 245-252, August.
    21. Barrett W. Thomas & Chelsea C. White, 2004. "Anticipatory Route Selection," Transportation Science, INFORMS, vol. 38(4), pages 473-487, November.
    22. Kevin Zhu, 2004. "Information Transparency of Business-to-Business Electronic Markets: A Game-Theoretic Analysis," Management Science, INFORMS, vol. 50(5), pages 670-685, May.
    23. Gregory A. Godfrey & Warren B. Powell, 2002. "An Adaptive Dynamic Programming Algorithm for Dynamic Fleet Management, II: Multiperiod Travel Times," Transportation Science, INFORMS, vol. 36(1), pages 40-54, February.
    24. Warren B. Powell, 1996. "A Stochastic Formulation of the Dynamic Assignment Problem, with an Application to Truckload Motor Carriers," Transportation Science, INFORMS, vol. 30(3), pages 195-219, August.
    25. Stewart, William R. & Golden, Bruce L., 1983. "Stochastic vehicle routing: A comprehensive approach," European Journal of Operational Research, Elsevier, vol. 14(4), pages 371-385, December.
    26. Jian Yang & Patrick Jaillet & Hani Mahmassani, 2004. "Real-Time Multivehicle Truckload Pickup and Delivery Problems," Transportation Science, INFORMS, vol. 38(2), pages 135-148, May.
    27. Dominique Feillet & Pierre Dejax & Michel Gendreau, 2005. "Traveling Salesman Problems with Profits," Transportation Science, INFORMS, vol. 39(2), pages 188-205, May.
    Full references (including those not matched with items on IDEAS)

    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. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    2. Zolfagharinia, Hossein & Haughton, Michael, 2018. "The importance of considering non-linear layover and delay costs for local truckers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 331-355.
    3. Zolfagharinia, Hossein & Haughton, Michael A., 2017. "Operational flexibility in the truckload trucking industry," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 437-460.
    4. Zolfagharinia, Hossein & Haughton, Michael, 2016. "Effective truckload dispatch decision methods with incomplete advance load information," European Journal of Operational Research, Elsevier, vol. 252(1), pages 103-121.
    5. Cheung, Bernard K.-S. & Choy, K.L. & Li, Chung-Lun & Shi, Wenzhong & Tang, Jian, 2008. "Dynamic routing model and solution methods for fleet management with mobile technologies," International Journal of Production Economics, Elsevier, vol. 113(2), pages 694-705, June.
    6. Lars M. Hvattum & Arne Løkketangen & Gilbert Laporte, 2006. "Solving a Dynamic and Stochastic Vehicle Routing Problem with a Sample Scenario Hedging Heuristic," Transportation Science, INFORMS, vol. 40(4), pages 421-438, November.
    7. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    8. Barrett W. Thomas, 2007. "Waiting Strategies for Anticipating Service Requests from Known Customer Locations," Transportation Science, INFORMS, vol. 41(3), pages 319-331, August.
    9. Zolfagharinia, Hossein & Haughton, Michael, 2014. "The benefit of advance load information for truckload carriers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 70(C), pages 34-54.
    10. Al Hajj Hassan, Lama & Hewitt, Mike & Mahmassani, Hani S., 2022. "Daily load planning under different autonomous truck deployment scenarios," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 166(C).
    11. Soumia Ichoua & Michel Gendreau & Jean-Yves Potvin, 2006. "Exploiting Knowledge About Future Demands for Real-Time Vehicle Dispatching," Transportation Science, INFORMS, vol. 40(2), pages 211-225, May.
    12. Martijn Mes & Matthieu Heijden & Peter Schuur, 2013. "Interaction between intelligent agent strategies for real-time transportation planning," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 21(2), pages 337-358, March.
    13. Soeffker, Ninja & Ulmer, Marlin W. & Mattfeld, Dirk C., 2022. "Stochastic dynamic vehicle routing in the light of prescriptive analytics: A review," European Journal of Operational Research, Elsevier, vol. 298(3), pages 801-820.
    14. Marlin W. Ulmer & Dirk C. Mattfeld & Felix Köster, 2018. "Budgeting Time for Dynamic Vehicle Routing with Stochastic Customer Requests," Transportation Science, INFORMS, vol. 52(1), pages 20-37, January.
    15. Mathias A. Klapp & Alan L. Erera & Alejandro Toriello, 2018. "The One-Dimensional Dynamic Dispatch Waves Problem," Transportation Science, INFORMS, vol. 52(2), pages 402-415, March.
    16. Stefan Vonolfen & Michael Affenzeller, 2016. "Distribution of waiting time for dynamic pickup and delivery problems," Annals of Operations Research, Springer, vol. 236(2), pages 359-382, January.
    17. Marlin W. Ulmer & Justin C. Goodson & Dirk C. Mattfeld & Marco Hennig, 2019. "Offline–Online Approximate Dynamic Programming for Dynamic Vehicle Routing with Stochastic Requests," Service Science, INFORMS, vol. 53(1), pages 185-202, February.
    18. Ji, Chenlu & Mandania, Rupal & Liu, Jiyin & Liret, Anne, 2022. "Scheduling on-site service deliveries to minimise the risk of missing appointment times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    19. Stefan Vonolfen & Michael Affenzeller, 2016. "Distribution of waiting time for dynamic pickup and delivery problems," Annals of Operations Research, Springer, vol. 236(2), pages 359-382, January.
    20. Allahviranloo, Mahdieh & Chow, Joseph Y.J. & Recker, Will W., 2014. "Selective vehicle routing problems under uncertainty without recourse," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 62(C), pages 68-88.

    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:inm:ortrsc:v:41:y:2007:i:3:p:302-318. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.