IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v152y2021icp140-179.html
   My bibliography  Save this article

Synchronizing time-dependent transportation services: Reformulation and solution algorithm using quadratic assignment problem

Author

Listed:
  • Wu, Xin (Bruce)
  • Lu, Jiawei
  • Wu, Shengnan
  • Zhou, Xuesong (Simon)

Abstract

A new modeling framework is developed in this paper to design a class of synchronized transportation services that can be formulated as a time-dependent synchronized service network design problem. The framework is established using a generic network representation for the quadratic assignment problem (QAP). As one of the fundamental combinatorial optimization problems, the QAP was introduced by Koopmans and Beckman (KB-QAP), in 1957, in the context of locating economic activities. Our proposed network-based QAP (NET-QAP) model not only linearizes the KB-QAP model but also generalizes the traditional QAP model as a special case with a symmetric network structure. The NET-QAP is utilized to formulate a time-dependent synchronized service network design problem to obtain an optimal schedule for both inbound and outbound services in a transshipment area, where commodities are collected from origins using the inbound services and distributed to their final destinations using the outbound services (after sorting and storage). From the view of the Gilmore-Lawler Bound (GLB), this paper explores a new branch and bound framework to solve the synchronizing NET-QAP problem. An extended GLB (E-QAP) is adopted in this research as a lower bound estimator for the first-stage assignment costs, based on several relaxed subproblems in the second-stage assignment. Then, the framework can also be applied to estimate the cost of sub-decisions that are involved in making a broader decision-making problem. Numerical experiments are conducted to demonstrate the effectiveness and applicability of the proposed modeling and computational framework.

Suggested Citation

  • Wu, Xin (Bruce) & Lu, Jiawei & Wu, Shengnan & Zhou, Xuesong (Simon), 2021. "Synchronizing time-dependent transportation services: Reformulation and solution algorithm using quadratic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 152(C), pages 140-179.
  • Handle: RePEc:eee:transb:v:152:y:2021:i:c:p:140-179
    DOI: 10.1016/j.trb.2021.08.008
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261521001582
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.trb.2021.08.008?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. Liu, Jiangtao & Zhou, Xuesong, 2016. "Capacitated transit service network design with boundedly rational agents," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 225-250.
    2. Ball, Michael O. & Kaku, Bharat K. & Vakhutinsky, Andrew, 1998. "Network-based formulations of the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 104(1), pages 241-249, January.
    3. Christian Liebchen, 2008. "The First Optimized Railway Timetable in Practice," Transportation Science, INFORMS, vol. 42(4), pages 420-435, November.
    4. Matteo Fischetti & Michele Monaci & Domenico Salvagnin, 2012. "Three Ideas for the Quadratic Assignment Problem," Operations Research, INFORMS, vol. 60(4), pages 954-964, August.
    5. Natashia L. Boland & Martin W. P. Savelsbergh, 2019. "Perspectives on integer programming for time-dependent models," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 27(2), pages 147-173, July.
    6. Wu, Xin & Nie, Lei & Xu, Meng & Yan, Fei, 2018. "A perishable food supply chain problem considering demand uncertainty and time deadline constraints: Modeling and application to a high-speed railway catering service," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 111(C), pages 186-209.
    7. Wu, Xin & Nie, Lei & Xu, Meng & Zhao, Lili, 2019. "Distribution planning problem for a high-speed rail catering service considering time-varying demands and pedestrian congestion: A lot-sizing-based model and decomposition algorithm," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 123(C), pages 61-89.
    8. Shi, Tie & Zhou, Xuesong, 2015. "A mixed integer programming model for optimizing multi-level operations process in railroad yards," Transportation Research Part B: Methodological, Elsevier, vol. 80(C), pages 19-39.
    9. Skorin-Kapov, Darko & Skorin-Kapov, Jadranka & O'Kelly, Morton, 1996. "Tight linear programming relaxations of uncapacitated p-hub median problems," European Journal of Operational Research, Elsevier, vol. 94(3), pages 582-593, November.
    10. Los, Marc, 1978. "Simultaneous optimization of land use and transportation : A synthesis of the quadratic assignment problem and the optimal network problem," Regional Science and Urban Economics, Elsevier, vol. 8(1), pages 21-42, February.
    11. Meng, Qiang & Wang, Xinchang, 2011. "Intermodal hub-and-spoke network design: Incorporating multiple stakeholders and multi-type containers," Transportation Research Part B: Methodological, Elsevier, vol. 45(4), pages 724-742, May.
    12. Natashia Boland & Mike Hewitt & Luke Marshall & Martin Savelsbergh, 2017. "The Continuous-Time Service Network Design Problem," Operations Research, INFORMS, vol. 65(5), pages 1303-1321, October.
    13. Boyce, D. E. & Janson, B. N., 1980. "A discrete transportation network design problem with combined trip distribution and assignment," Transportation Research Part B: Methodological, Elsevier, vol. 14(1-2), pages 147-154.
    14. Giusti, Riccardo & Manerba, Daniele & Bruno, Giorgio & Tadei, Roberto, 2019. "Synchromodal logistics: An overview of critical success factors, enabling technologies, and open research issues," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 129(C), pages 92-110.
    15. Scherr, Yannick Oskar & Neumann Saavedra, Bruno Albert & Hewitt, Mike & Mattfeld, Dirk Christian, 2019. "Service network design with mixed autonomous fleets," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 124(C), pages 40-55.
    16. Ebery, Jamie & Krishnamoorthy, Mohan & Ernst, Andreas & Boland, Natashia, 2000. "The capacitated multiple allocation hub location problem: Formulations and algorithms," European Journal of Operational Research, Elsevier, vol. 120(3), pages 614-631, February.
    17. Eugene L. Lawler, 1963. "The Quadratic Assignment Problem," Management Science, INFORMS, vol. 9(4), pages 586-599, July.
    18. SteadieSeifi, M. & Dellaert, N.P. & Nuijten, W. & Van Woensel, T. & Raoufi, R., 2014. "Multimodal freight transportation planning: A literature review," European Journal of Operational Research, Elsevier, vol. 233(1), pages 1-15.
    19. Carlos F. Daganzo, 1986. "Static Blocking at Railyards: Sorting Implications and Track Requirements," Transportation Science, INFORMS, vol. 20(3), pages 189-199, August.
    20. Heffley, Dennis R, 1972. "The Quadratic Assignment Problem: A Note," Econometrica, Econometric Society, vol. 40(6), pages 1155-1163, November.
    21. Gao, Ziyou & Wu, Jianjun & Sun, Huijun, 2005. "Solution algorithm for the bi-level discrete network design problem," Transportation Research Part B: Methodological, Elsevier, vol. 39(6), pages 479-495, July.
    22. Mahmoudi, Monirehalsadat & Zhou, Xuesong, 2016. "Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state–space–time network representations," Transportation Research Part B: Methodological, Elsevier, vol. 89(C), pages 19-42.
    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. Zhang, Yongxiang & Peng, Qiyuan & Lu, Gongyuan & Zhong, Qingwei & Yan, Xu & Zhou, Xuesong, 2022. "Integrated line planning and train timetabling through price-based cross-resolution feedback mechanism," Transportation Research Part B: Methodological, Elsevier, vol. 155(C), pages 240-277.
    2. Yameng Wang & Zhe Chen & Xiumei Wang & Mengyang Hou & Feng Wei, 2021. "Research on the Spatial Network Structure and Influencing Factors of the Allocation Efficiency of Agricultural Science and Technology Resources in China," Agriculture, MDPI, vol. 11(11), pages 1-23, November.

    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. Loiola, Eliane Maria & de Abreu, Nair Maria Maia & Boaventura-Netto, Paulo Oswaldo & Hahn, Peter & Querido, Tania, 2007. "A survey for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 176(2), pages 657-690, January.
    2. Wu, Xin & Nie, Lei & Xu, Meng & Zhao, Lili, 2019. "Distribution planning problem for a high-speed rail catering service considering time-varying demands and pedestrian congestion: A lot-sizing-based model and decomposition algorithm," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 123(C), pages 61-89.
    3. Feizollahi, Mohammad Javad & Feyzollahi, Hadi, 2015. "Robust quadratic assignment problem with budgeted uncertain flows," Operations Research Perspectives, Elsevier, vol. 2(C), pages 114-123.
    4. Jiahao Zhao & Xiaoning Zhu & Li Wang, 2020. "Study on Scheme of Outbound Railway Container Organization in Rail-Water Intermodal Transportation," Sustainability, MDPI, vol. 12(4), pages 1-18, February.
    5. Milad Keshvari Fard & Laurent Alfandari, 2018. "Trade-offs between the Stepwise Cost Function and its Linear Approximation for the Modular Hub Location Problem," Working Papers hal-01821280, HAL.
    6. Zhao, Meng & Li, Xiaopeng & Yin, Jiateng & Cui, Jianxun & Yang, Lixing & An, Shi, 2018. "An integrated framework for electric vehicle rebalancing and staff relocation in one-way carsharing systems: Model formulation and Lagrangian relaxation-based solution approach," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 542-572.
    7. Zhang, Yongxiang & Peng, Qiyuan & Lu, Gongyuan & Zhong, Qingwei & Yan, Xu & Zhou, Xuesong, 2022. "Integrated line planning and train timetabling through price-based cross-resolution feedback mechanism," Transportation Research Part B: Methodological, Elsevier, vol. 155(C), pages 240-277.
    8. Milad , Keshvari Fard & Laurent, Alfandari, 2018. "Trade-offs between the Stepwise Cost Function and its Linear Approximation for the Modular Hub Location Problem," ESSEC Working Papers WP1805, ESSEC Research Center, ESSEC Business School.
    9. Dhyani, Sneha & Jayaswal, Sachin & Sinha, Ankur & Vidyarthi, Navneet, 2019. "Alternate Second Order Conic Programming Reformulations for Hub Location with Capacity Selection under Demand," IIMA Working Papers WP 2018-12-04, Indian Institute of Management Ahmedabad, Research and Publication Department.
    10. de Lima, Vinícius L. & Alves, Cláudio & Clautiaux, François & Iori, Manuel & Valério de Carvalho, José M., 2022. "Arc flow formulations based on dynamic programming: Theoretical foundations and applications," European Journal of Operational Research, Elsevier, vol. 296(1), pages 3-21.
    11. Zhang, Yongxiang & Peng, Qiyuan & Yao, Yu & Zhang, Xin & Zhou, Xuesong, 2019. "Solving cyclic train timetabling problem through model reformulation: Extended time-space network construct and Alternating Direction Method of Multipliers methods," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 344-379.
    12. Yang, Lixing & Zhou, Xuesong, 2017. "Optimizing on-time arrival probability and percentile travel time for elementary path finding in time-dependent transportation networks: Linear mixed integer programming reformulations," Transportation Research Part B: Methodological, Elsevier, vol. 96(C), pages 68-91.
    13. Chen, Jingxu & Wang, Shuaian & Liu, Zhiyuan & Guo, Yanyong, 2018. "Network-based optimization modeling of manhole setting for pipeline transportation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 113(C), pages 38-55.
    14. Alumur, Sibel A. & Kara, Bahar Y. & Karasan, Oya E., 2012. "Multimodal hub location and hub network design," Omega, Elsevier, vol. 40(6), pages 927-939.
    15. Sneha Dhyani Bhatt & Sachin Jayaswal & Ankur Sinha & Navneet Vidyarthi, 2021. "Alternate second order conic program reformulations for hub location under stochastic demand and congestion," Annals of Operations Research, Springer, vol. 304(1), pages 481-527, September.
    16. Zhang, Yimeng & Li, Xinlei & van Hassel, Edwin & Negenborn, Rudy R. & Atasoy, Bilge, 2022. "Synchromodal transport planning considering heterogeneous and vague preferences of shippers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    17. Li, Wenjie & Yang, Lixing & Wang, Li & Zhou, Xuesong & Liu, Ronghui & Gao, Ziyou, 2017. "Eco-reliable path finding in time-variant and stochastic networks," Energy, Elsevier, vol. 121(C), pages 372-387.
    18. Di, Zhen & Yang, Lixing & Qi, Jianguo & Gao, Ziyou, 2018. "Transportation network design for maximizing flow-based accessibility," Transportation Research Part B: Methodological, Elsevier, vol. 110(C), pages 209-238.
    19. Murat Köksalan & Banu Soylu, 2010. "Bicriteria p -Hub Location Problems and Evolutionary Algorithms," INFORMS Journal on Computing, INFORMS, vol. 22(4), pages 528-542, November.
    20. Alumur, Sibel A. & Nickel, Stefan & Saldanha-da-Gama, Francisco, 2012. "Hub location under uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 46(4), pages 529-543.

    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:transb:v:152:y:2021:i:c:p:140-179. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: . General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    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/wps/find/journaldescription.cws_home/548/description#description .

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.