Skip to main content
SpringerLink
Log in

Modelling and solving an m-location, n-courier, priority-based planning problem on a network

  • General Paper
  • Published:
Journal of the Operational Research Society

Abstract

In this paper, we study an m-location, n-courier, priority-based planning problem on a network, which we refer to as the Courier Planning Problem (CPP). The CPP arises on a daily basis in the context of planning the transportation of materials and personnel in peacetime for the Turkish Armed Forces. The main issue addressed in CPP is to transport as many of deliverables as possible from their origins to their destinations via a fleet of transportation assets (couriers) that operate at fixed routes and schedules. Priorities must be taken into account and constraints on the routes, operating schedules, and capacities of the transportation assets must be obeyed. Time windows may be specified for some or all transportation requests and must be satisfied. We study the CPP as well as its two extensions, and present integer programming formulations based on the multi-commodity flow structure. The formulations are tested on real world-based data and display satisfactory computational performance. Our main contributions are to develop an effective formulation scheme for a complicated large-scale real world problem and to demonstrate that such problems are solvable via commercial general purpose solvers through meticulous modelling.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5

Similar content being viewed by others

References

  • Akgün I and Tansel B (2007). Optimization of transportation requirements in the deployment of military units. Comput Opns Res 34: 1158–1176.

    Article  Google Scholar 

  • Baker SF, Morton DP, Rosenthal RE and Williams LM (1999). Optimizing strategic airlift. Technical Report NPS-OR-99-004, Naval Postgraduate School, Monterey, CA.

  • Baker SF, Morton DP, Rosenthal RE and Williams LM (2002). Optimizing military airlift. Opns Res 50: 582–602.

    Article  Google Scholar 

  • Baveja A and Srinivasan A (2000). Approximation algorithms for disjoint paths and related routing and packing problems. Math Opns Res 25: 255–280.

    Article  Google Scholar 

  • Bazaraa MS, Jarvis JJ and Sherali HD (1990). Linear Programming and Network Flows. Wiley: New York.

  • Berbeglia G, Cordeau J-F, Gribkovskaia I and Laporte G (2007). Static pickup and delivery problems: A classification scheme and survey. TOP 15: 1–13.

    Article  Google Scholar 

  • Cormen TH, Leiserson CE and Rivest RL (2000). Introduction to Algorithms. MIT Press: Cambridge, MA.

    Google Scholar 

  • Ford LR and Fulkerson DR (1956). Maximal flow through a network. Can J Math 8: 399–404.

    Article  Google Scholar 

  • Fréville A (2004). The multidimensional 0-1 knapsack problem: An overview. Eur J Opl Res 155: 1–21.

    Article  Google Scholar 

  • Fulkerson DR and Dantzig GB (1955). Computation of maximal flow in networks. Nav Res Log Q 2: 277–283.

    Article  Google Scholar 

  • Garey MR and Johnson DS (1979). Computers and Intractability. Bell Telephone Laboratories: Murray Hill, NJ.

    Google Scholar 

  • Grinold RC (1968). A multicommodity max-flow algorithm. Opns Res 16: 1234–1238.

    Article  Google Scholar 

  • Grinold RC (1969). A note on multicommodity max-flow. Opns Res 17: 755.

    Article  Google Scholar 

  • Guruswami V, Khanna S, Rajaraman R, Shepherd B and Yannakakis M (2003). Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J Comput Syst Sci 67: 473–496.

    Article  Google Scholar 

  • Karp RM (1975). On the computational complexity of combinatorial problems. Networks 5: 45–68.

    Google Scholar 

  • Kleinberg J (1996). Approximation algorithms for disjoint paths problems. PhD thesis, Massachusetts Institute of Technology.

  • Kolliopoulos SG and Stein C (2002). Approximation algorithms for single-source unsplittable flow. SIAM J Computing 31: 919–946.

    Article  Google Scholar 

  • Kolman P and Scheideler C (2006). Improved bounds for the unsplittable flow problem. J Algorithm 61: 20–44.

    Article  Google Scholar 

  • Sherali HD (1982). Equivalent weights for lexicographic multi-objective programs: Characterizations and computations. Eur J Opl Res 11: 367–379.

    Article  Google Scholar 

Download references

Acknowledgements

Thanks are due to the referees for their valuable comments.

Author information

Authors and Affiliations

  1. Ozyegin University, Üsküdar, Turkey

    G Erdoğan

  2. Bilkent University, Bilkent, Turkey

    B Tansel & İ Akgün

Authors
  1. G Erdoğan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. B Tansel
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. İ Akgün
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to G Erdoğan.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Erdoğan, G., Tansel, B. & Akgün, İ. Modelling and solving an m-location, n-courier, priority-based planning problem on a network. J Oper Res Soc 63, 2–15 (2012). https://doi.org/10.1057/jors.2011.8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2011.8

Keywords

Search

Navigation