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

The Partitioning Min–Max Weighted Matching Problem

Author

Listed:
  • Kress, Dominik
  • Meiswinkel, Sebastian
  • Pesch, Erwin

Abstract

We introduce and analyze the Partitioning Min–Max Weighted Matching (PMMWM) Problem. PMMWM combines the problem of partitioning a set of vertices of a bipartite graph into disjoint subsets of restricted size and the strongly NP-hard Min–Max Weighted Matching (MMWM) Problem, that has recently been introduced in the literature. In contrast to PMMWM, the latter problem assumes the partitioning to be given. Applications arise in the field of intermodal container terminals and sea ports. We propose a MILP formulation for PMMWM and prove that the problem is NP-hard in the strong sense. Two heuristic frameworks are presented. Both of them outperform standard optimization software. Our extensive computational study proves that the algorithms provide high quality solutions within reasonable time.

Suggested Citation

  • Kress, Dominik & Meiswinkel, Sebastian & Pesch, Erwin, 2015. "The Partitioning Min–Max Weighted Matching Problem," European Journal of Operational Research, Elsevier, vol. 247(3), pages 745-754.
    • Handle: RePEc:eee:ejores:v:247:y:2015:i:3:p:745-754
    DOI: 10.1016/j.ejor.2015.06.041
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722171500555X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2015.06.041?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. Boysen, Nils & Fliedner, Malte, 2010. "Determining crane areas in intermodal transshipment yards: The yard partition problem," European Journal of Operational Research, Elsevier, vol. 204(2), pages 336-342, July.
    2. Nils Boysen & Malte Fliedner & Florian Jaehn & Erwin Pesch, 2013. "A Survey on Container Processing in Railway Yards," Transportation Science, INFORMS, vol. 47(3), pages 312-329, August.
    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. Schulz, Arne & Fliedner, Malte & Fiedrich, Benedikt & Pfeiffer, Christian, 2021. "Levelling crane workload in multi-yard rail-road container terminals," European Journal of Operational Research, Elsevier, vol. 293(3), pages 941-954.
    2. Kress, Dominik & Meiswinkel, Sebastian & Pesch, Erwin, 2019. "Straddle carrier routing at seaport container terminals in the presence of short term quay crane buffer areas," European Journal of Operational Research, Elsevier, vol. 279(3), pages 732-750.
    3. Basallo-Triana, Mario José & Bravo-Bastidas, Juan José & Vidal-Holguín, Carlos Julio, 2022. "A rail-road transshipment yard picture," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 159(C).

    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. Lennart Zey & Dirk Briskorn & Nils Boysen, 2022. "Twin-crane scheduling during seaside workload peaks with a dedicated handshake area," Journal of Scheduling, Springer, vol. 25(1), pages 3-34, February.
    2. Martin Tschöke & Nils Boysen, 2018. "Container supply with multi-trailer trucks: parking strategies to speed up the gantry crane-based loading of freight trains in rail yards," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(2), pages 319-339, March.
    3. Basallo-Triana, Mario José & Bravo-Bastidas, Juan José & Vidal-Holguín, Carlos Julio, 2022. "A rail-road transshipment yard picture," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 159(C).
    4. Stefan Fedtke & Nils Boysen, 2017. "Gantry crane and shuttle car scheduling in modern rail–rail transshipment yards," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(2), pages 473-503, March.
    5. Alena Otto & Xiyu Li & Erwin Pesch, 2017. "Two-Way Bounded Dynamic Programming Approach for Operations Planning in Transshipment Yards," Transportation Science, INFORMS, vol. 51(1), pages 325-342, February.
    6. Konrad Stephan & Nils Boysen, 2017. "Crane scheduling in railway yards: an analysis of computational complexity," Journal of Scheduling, Springer, vol. 20(5), pages 507-526, October.
    7. Schulz, Arne & Fliedner, Malte & Fiedrich, Benedikt & Pfeiffer, Christian, 2021. "Levelling crane workload in multi-yard rail-road container terminals," European Journal of Operational Research, Elsevier, vol. 293(3), pages 941-954.
    8. Nils Boysen & Joachim Scholl & Konrad Stephan, 2017. "When road trains supply freight trains: scheduling the container loading process by gantry crane between multi-trailer trucks and freight trains," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(1), pages 137-164, January.
    9. Maksim Barketau & Erwin Pesch & Yakov Shafransky, 2016. "Scheduling dedicated jobs with variative processing times," Journal of Combinatorial Optimization, Springer, vol. 31(2), pages 774-785, February.
    10. Gang Ren & Xiaohan Wang & Jiaxin Cai & Shujuan Guo, 2021. "Allocation and Scheduling of Handling Resources in the Railway Container Terminal Based on Crossing Crane Area," Sustainability, MDPI, vol. 13(3), pages 1-24, January.
    11. Leachman, Robert C. & Jula, Payman, 2012. "Estimating flow times for containerized imports from Asia to the United States through the Western rail network," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 296-309.
    12. Michael F. Gorman & John-Paul Clarke & Amir Hossein Gharehgozli & Michael Hewitt & René de Koster & Debjit Roy, 2014. "State of the Practice: A Review of the Application of OR/MS in Freight Transportation," Interfaces, INFORMS, vol. 44(6), pages 535-554, December.
    13. Shujuan Guo & Cuijie Diao & Gang Li & Katsuhiko Takahashi, 2021. "The Two-Echelon Dual-Channel Models for the Intermodal Container Terminals of the China Railway Express Considering Container Accumulation Modes," Sustainability, MDPI, vol. 13(5), pages 1-19, March.
    14. Yan, Baicheng & Jin, Jian Gang & Zhu, Xiaoning & Lee, Der-Horng & Wang, Li & Wang, Hua, 2020. "Integrated planning of train schedule template and container transshipment operation in seaport railway terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 142(C).
    15. Mantovani, Serena & Morganti, Gianluca & Umang, Nitish & Crainic, Teodor Gabriel & Frejinger, Emma & Larsen, Eric, 2018. "The load planning problem for double-stack intermodal trains," European Journal of Operational Research, Elsevier, vol. 267(1), pages 107-119.
    16. Nils Boysen & Malte Fliedner & Florian Jaehn & Erwin Pesch, 2013. "A Survey on Container Processing in Railway Yards," Transportation Science, INFORMS, vol. 47(3), pages 312-329, August.
    17. Nils Boysen & Simon Emde & Malte Fliedner, 2016. "The basic train makeup problem in shunting yards," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(1), pages 207-233, January.
    18. Boysen, Nils & Briskorn, Dirk & Emde, Simon, 2017. "Sequencing of picking orders in mobile rack warehouses," European Journal of Operational Research, Elsevier, vol. 259(1), pages 293-307.
    19. Roy, Debjit & van Ommeren, Jan-Kees & de Koster, René & Gharehgozli, Amir, 2022. "Modeling landside container terminal queues: Exact analysis and approximations," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 73-102.
    20. Boysen, Nils & Briskorn, Dirk & Fedtke, Stefan & Schmickerath, Marcel, 2019. "Automated sortation conveyors: A survey from an operational research perspective," European Journal of Operational Research, Elsevier, vol. 276(3), pages 796-815.

    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:247:y:2015:i:3:p:745-754. 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.