[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Constraint Programming and Local Search Heuristic: a Matheuristic Approach for Routing and Scheduling Feeder Vessels in Multi-terminal Ports

  • Original Research
  • Published:
SN Operations Research Forum Aims and scope Submit manuscript

Abstract

In the liner shipping business, shipping ports represent the main nodes in the maritime transportation network. These ports have a collection of terminals where container vessels can load and discharge containers. However, the logistics and planning of operations differ depending on the vessel size. Large container vessels visit a single terminal, whereas smaller container vessels, or feeder vessels, visit several terminals to transport all containers within the multiple terminals of the port. In this paper, we study the Port Scheduling Problem, the problem of scheduling the operations of feeder vessels in multi-terminal ports. The resulting problem can be identified as a version of the General Shop Scheduling Problem. We consider a Constraint Programming formulation of the problem, and we propose a matheuristic solution approach for solving large instances. The proposed matheuristic is a hybrid solution method that combines Constraint Programming with a local search heuristic. The solution approach benefits from the fast search capabilities of local search algorithms to explore the solution space using an Adaptive Large Neighbourhood Search heuristic. During the search, we further use the Constraint Programming model as an intensification technique, every time a new best-known solution is found. We conduct detailed computational experiments on the PortLib instances, showing that the incorporation of Constraint Programming within the heuristic search can result in significant benefits. The high instability in solution quality obtained by local search heuristics can be lowered by a simple combination of both methods.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

Notes

  1. https://doi.org/10.5281/zenodo.3820078

  2. https://doi.org/10.5281/zenodo.3820078

  3. https://doi.org/10.5281/zenodo.3820078

References

  1. Aldous D, Vazirani U (1994) “Go with the winners” algorithms. In: Proceedings 35th annual symposium on foundations of computer science. IEEE, pp 492–501

  2. Ameln M, Sand Fuglum J, Thun K, Andersson H, Stålhane M (2019) A new formulation for the liner shipping network design problem. Int Trans Oper Res

  3. Baptiste P, Le Pape C, Nuijten W (2012) Constraint-based scheduling: applying constraint programming to scheduling problems, vol 39. Springer Science & Business Media, New York

    Google Scholar 

  4. Beck JC, Feng T, Watson J-P (2011) Combining constraint programming and local search for job-shop scheduling. INFORMS J Comput 23(1):1–14

    Article  Google Scholar 

  5. Bierwirth C, Meisel F (2015) A follow-up survey of berth allocation and quay crane scheduling problems in container terminals. Eur J Oper Res 244 (3):675–689

    Article  Google Scholar 

  6. Boschetti MA, Maniezzo V, Roffilli M, Röhler AB (2009) Matheuristics: optimization, simulation and control. In: International workshop on hybrid metaheuristics. Springer, pp 171–177

  7. Brucker P (1999) Scheduling algorithms. J-Oper Res Soc 50

  8. Christiansen M, Fagerholt K, Nygreen B, Ronen D (2013) Ship routing and scheduling in the new millennium. Eur J Oper Res 228(3):467–483

    Article  Google Scholar 

  9. Christiansen M, Hellsten E, Pisinger D, Sacramento D, Vilhelmsen C (2020) Liner shipping network design. Eur J Oper Res. In press. European J. Oper. Res. 286(1):1–20

    Article  Google Scholar 

  10. De Backer B, Furnon V, Shaw P, Kilby P, Prosser P (2000) Solving vehicle routing problems using constraint programming and metaheuristics. J Heuristics 6(4):501–523

    Article  Google Scholar 

  11. Fleszar K, Hindi KS (2018) Algorithms for the unrelated parallel machine scheduling problem with a resource constraint. Eur J Oper Res 271 (3):839–848

    Article  Google Scholar 

  12. Gedik R, Kalathia D, Egilmez G, Kirac E (2018) A constraint programming approach for solving unrelated parallel machine scheduling problem. Comput Ind Eng 121:139–149

    Article  Google Scholar 

  13. Gerhards P, Stuerck C, Fink A (2017) An adaptive large neighbourhood search as a matheuristic for the multi-mode resource-constrained project scheduling problem. Eur J Ind Eng 11(6):774–791

    Article  Google Scholar 

  14. Gharehgozli AH, Roy D, de Koster R (2016) Sea container terminals: new technologies and OR models. Marit Econ Logist 18(2):103–140

    Article  Google Scholar 

  15. Gökgür B, Hnich B, Özpeynirci S (2018) Parallel machine scheduling with tool loading: a constraint programming approach. Int J Prod Res 56(16):5541–5557

    Article  Google Scholar 

  16. Graham RL, Lawler EL, Lenstra JK, Kan AR (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey, vol 5. Elsevier, pp 287–326

  17. Grimes D, Hebrard E, Malapert A (2009) Closing the open shop: contradicting conventional wisdom. In: International conference on principles and practice of constraint programming. Springer, pp 400–408

  18. Hellsten E, Sacramento D, Pisinger D (2020) An adaptive large neighbourhood search heuristic for routing and scheduling feeder vessels in multi-terminal ports. European J. Oper. Res. 287(2):682–698

    Article  Google Scholar 

  19. Hojabri H, Gendreau M, Potvin J-Y, Rousseau L-M (2018) Large neighborhood search with constraint programming for a vehicle routing problem with synchronization constraints. Comput Oper Res 92:87–97

    Article  Google Scholar 

  20. Kaveshgar N, Huynh N, Rahimian SK (2012) An efficient genetic algorithm for solving the quay crane scheduling problem. Expert Syst Appl 39 (18):13108–13117

    Article  Google Scholar 

  21. Kim KH, Moon KC (2003) Berth scheduling by simulated annealing. Transport Res B Methodol 37(6):541–560

    Article  Google Scholar 

  22. Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220(4598):671–680

    Article  Google Scholar 

  23. Kizilay D, Eliiyi DT, Van Hentenryck P (2018) Constraint and mathematical programming models for integrated port container terminal operations. In: International conference on the integration of constraint programming, artificial intelligence, and operations research. Springer, pp 344–360

  24. Kovacs AA, Parragh SN, Doerner KF, Hartl RF (2012) Adaptive large neighborhood search for service technician routing and scheduling problems. J Sched 15(5):579–600

    Article  Google Scholar 

  25. Laborie P, Rogerie J, Shaw P, Vilím P (2018) IBM ILOG CP optimizer for scheduling. Constraints 23(2):210–250

    Article  Google Scholar 

  26. Lin S-W, Ting C-J (2014) Solving the dynamic berth allocation problem by simulated annealing. Eng Optim 46(3):308–327

    Article  Google Scholar 

  27. Malapert A, Cambazard H, Guéret C, Jussien N, Langevin A, Rousseau L-M (2012) An optimal constraint programming approach to the open-shop problem. INFORMS J Comput 24(2):228–244

    Article  Google Scholar 

  28. Meisel F (2009) Contributions to Management Science Seaside operations planning in container terminals. Springer, Berlin

  29. Montazeri M, Van Wassenhove L (1990) Analysis of scheduling rules for an fms. Int J Prod Res 28(4):785–802

    Article  Google Scholar 

  30. Msakni MK, Fagerholt K, Meisel F, Lindstad E (2020) Analyzing different designs of liner shipping feeder networks: a case study. Transp Res E Logist Transp Rev 101839:134

    Google Scholar 

  31. Pinedo M (2012) Theory, algorithms, and systems Scheduling, Fourth. Springer, Berlin, p xx+ 673

  32. Poli R, Kennedy J, Blackwell T (2007) Particle swarm optimization. Swarm Intell 1(1):33–57

    Article  Google Scholar 

  33. Qin T, Du Y, Chen JH, Sha M (2020) Combining mixed integer programming and constraint programming to solve the integrated scheduling problem of container handling operations of a single vessel. European J Oper Res 285(3):884–901

    Article  Google Scholar 

  34. Qin T, Du Y, Sha M (2016) Evaluating the solution performance of IP and CP for berth allocation with time-varying water depth. Transp Res E Logist Transp Rev 87:167–185

    Article  Google Scholar 

  35. Rifai AP, Nguyen H-T, Dawal SZM (2016) Multi-objective adaptive large neighborhood search for distributed reentrant permutation flow shop scheduling. Appl Soft Comput 40:42–57

    Article  Google Scholar 

  36. Ropke S, Pisinger D (2006) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation science 40(4):455–472

    Article  Google Scholar 

  37. Sacramento D, Pisinger D (2020) An iterative tabu-grasp based heuristic for the feeder network design problem. In: Proceedings of the TSL second triennial conference

  38. Sammarra M, Cordeau J-F, Laporte G, Monaco MF (2007) A tabu search heuristic for the quay crane scheduling problem. J Sched 10(4-5):327–336

    Article  Google Scholar 

  39. Santini A, Plum CE, Ropke S (2018a) A branch-and-price approach to the feeder network design problem. Eur J Oper Res 264(2):607–622

    Article  Google Scholar 

  40. Santini A, Ropke S, Hvattum LM (2018b) A comparison of acceptance criteria for the adaptive large neighbourhood search metaheuristic. J Heuristics 24(5):783–815

    Article  Google Scholar 

  41. Shaw P (1998) Using constraint programming and local search methods to solve vehicle routing problems. In: International conference on principles and practice of constraint programming. Springer, pp 417–431

  42. Stahlbock R, Voß S (2008) Operations research at container terminals: a literature update. OR Spectrum 30(1):1–52

    Article  Google Scholar 

  43. Talbi E-G (2016) Combining metaheuristics with mathematical programming, constraint programming and machine learning. Ann Oper Res 240 (1):171–215

    Article  Google Scholar 

  44. Unctad (2018) Review of maritime transport. Technical report, United Nations Conference on Trade and Development

  45. Unctad (2019) UnctadSTAT. https://unctadstat.unctad.org/wds/ReportFolders/reportFolders.aspx [Online; accessed December 9, 2019]

  46. Watson J-P, Beck JC (2008) A hybrid constraint programming/local search approach to the job-shop scheduling problem. In: International conference on integration of Artificial Intelligence (AI) and Operations Research (OR) techniques in constraint programming. Springer, pp 263–277

Download references

Author information

Authors and Affiliations

  1. DTU Management - Technical University of Denmark, Kongens Lyngby, Denmark

    David Sacramento & David Pisinger

  2. INSA Lyon, CITI, INRIA CHROMA, F-69621, Villeurbanne, France

    Christine Solnon

Authors
  1. David Sacramento
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Christine Solnon
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. David Pisinger
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to David Sacramento.

Ethics declarations

Conflict of Interest

The authors declare that they have no conflict of interest.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix: Algorithm procedure for the initial solution

Appendix: Algorithm procedure for the initial solution

We present the algorithm procedure for generating an initial solution. We propose a two-stage construction heuristic, which is further improved by a local search heuristic. The proposed algorithm is an extension of the algorithm procedure described in [18].

The procedure starts by generating an empty initial solution that only contains the dummy operations for the terminals and vessels from the set \(O\setminus \tilde {O}\). During the first stage, the heuristic iteratively adds the interior operations into the empty initial solution using the greedy insertion method, i.e. the operations are inserted into the current solution in the best position that minimise the current objective value. The procedure continues to generate a family of initial solutions at the next stage. During the second stage, we identify and remove all infeasible operations from the current solution. Following this, we again use the greedy insertion method to insert all the previously removed operations. The last stage is then repeated until a feasible solution is obtained or until the current infeasible solution cannot be further improved.

We consider different orders in which the operations can be inserted during the second stage of the construction heuristic. The sorting rules, inspired by the dispatching rules for scheduling problems [29], are presented below. The operations are sorted by: (1) No sorting, i.e. operations are sorted as they are removed; (2) earliest start of time windows; (3) latest start of time windows; (4) increasing size of time windows; (5) increasing service times; and (6) decreasing service times.

The method creates an initial solution for each sorting rule and then retrieves the solution with the lowest objective value as the initial solution. The pseudo-code for generating the initial solution can be seen below in Algorithm 2. Next, the initial solution is further improved by a simple local search heuristic, where the relocation of an operation is defined as a move in the neighbourhood.

figure b

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Sacramento, D., Solnon, C. & Pisinger, D. Constraint Programming and Local Search Heuristic: a Matheuristic Approach for Routing and Scheduling Feeder Vessels in Multi-terminal Ports. SN Oper. Res. Forum 1, 32 (2020). https://doi.org/10.1007/s43069-020-00036-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s43069-020-00036-x

Keywords

Search

Navigation