A Reservoir Balancing Constraint with Applications to Bike-Sharing | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Reservoir Balancing Constraint with Applications to Bike-Sharing

  • Conference paper
  • First Online:
Integration of AI and OR Techniques in Constraint Programming (CPAIOR 2016)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 9676))

Abstract

A global CP constraint is presented which improves the propagation of reservoir constraints on cumulative resources in schedules with optional tasks. The global constraint is incorporated in a CP approach to solve a Single-Commodity Pickup and Delivery Problem: the Bicycle Rebalancing Problem with Time-Windows and heterogeneous fleet. This problem was recently introduced at the 2015 ACP Summer School on Constraint Programming competition. The resulting CP approach outperforms a Branch-and-Bound approach derived from two closely related problems. In addition, the CP approach presented in this paper resulted in a first place position in the competition.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Observe that when x is a consumption event, i.e. \(q(x)<0\), then by definition, \(q_{max}(x)\) corresponds to the largest (least negative) value in the domain of q(x).

References

  1. ACP Summer School Constraint Programming Competition (2015). http://acpss2015.uconn.edu/competition/. Accessed July 2015

  2. Aggoun, A., Beldiceanu, N.: Extending chip in order to solve complex scheduling and placement problems. Math. Comput. Model. 17(7), 57–73 (1993). ISSN 0895-7177

    Article  Google Scholar 

  3. Bergman, D., Cire, A., van Hoeve, W.J.: Lagrangian bounds from decision diagrams. Constraints 20(3), 346–361 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  4. Dell’Amico, M., Hadjicostantinou, E., Iori, M., Novellani, S.: The bike sharing rebalancing problem: mathematical formulations and benchmark instances. Omega 45, 7–19 (2014)

    Article  Google Scholar 

  5. Desrochers, M., Laporte, G.: Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints. Oper. Res. Lett. 10(1), 27–36 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  6. Dror, M., Fortin, D., Roucairol, C.: Redistribution of self-service electric cars: a case of pickup and delivery. Research report RR-3543, INRIA, Projet PRAXITELE (1998). https://hal.inria.fr/inria-00073142

  7. Dumas, Y., Desrosiers, J., Gelinas, E., Solomon, M.M.: An optimal algorithm for the traveling salesman problem with time windows. Oper. Res. 43(2), 367–371 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  8. Gunes, C., van Hoeve, W.-J., Tayur, S.: Vehicle routing for food rescue programs: a comparison of different approaches. In: Lodi, A., Milano, M., Toth, P. (eds.) CPAIOR 2010. LNCS, vol. 6140, pp. 176–180. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  9. Hernández-Pérez, H., Salazar-González, J.J.: A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery. Discrete Appl. Math. 145(1), 126–139 (2004). ISSN 0166-218X

    Article  MathSciNet  MATH  Google Scholar 

  10. Hernández-Pérez, H., Salazar-González, J.J.: The one-commodity pickup-and-delivery traveling salesman problem: inequalities and algorithms. Networks 50(4), 258–272 (2007). ISSN 1097-0037

    Article  MathSciNet  MATH  Google Scholar 

  11. Kolisch, R.: Integrated scheduling, assembly area-and part-assignment forlarge-scale, make-to-order assemblies. Int. J. Prod. Econ. 64(13), 127–141 (2000)

    Article  Google Scholar 

  12. Laborie, P.: Algorithms for propagating resource constraints in AI planning and scheduling: existing approaches and new results. Artif. Intell. 143(2), 151–188 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  13. Laborie, P., Rogerie, J.: Reasoning with conditional time-intervals. In: FLAIRS Conference, pp. 555–560 (2008)

    Google Scholar 

  14. Laborie, P., Rogerie, J., Shaw, P., Vilím, P.: Reasoning with conditional time-intervals. Part II: an algebraical model for resources. In: FLAIRS Conference (2009)

    Google Scholar 

  15. Ropke, S., Cordeau, J.-F., Laporte, G.: Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Networks 49(4), 258–272 (2007). ISSN 0028-3045

    Article  MathSciNet  MATH  Google Scholar 

  16. Schutt, A., Feydy, T., Stuckey, P.J.: Explaining time-table-edge-finding propagation for the cumulative resource constraint. In: Gomes, C., Sellmann, M. (eds.) CPAIOR 2013. LNCS, vol. 7874, pp. 234–250. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  17. Simonis, H., Cornelissens, T.: Modelling producer/consumer constraints. In: Montanari, U., Rossi, F. (eds.) CP 1995. LNCS, vol. 976, pp. 449–462. Springer, Heidelberg (1995)

    Chapter  Google Scholar 

Download references

Acknowledgement

I would like to thank Philippe Laborie (IBM) for his many helpful suggestions and comments regarding the implementation of the Reservoir Balancing constraint.

Author information

Authors and Affiliations

  1. Robotics Institute and Tepper School of Business, Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA, 15213, USA

    Joris Kinable

Authors
  1. Joris Kinable
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Joris Kinable .

Editor information

Editors and Affiliations

  1. Université Laval, Quebec, Québec, Canada

    Claude-Guy Quimper

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing Switzerland

About this paper

Cite this paper

Kinable, J. (2016). A Reservoir Balancing Constraint with Applications to Bike-Sharing. In: Quimper, CG. (eds) Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2016. Lecture Notes in Computer Science(), vol 9676. Springer, Cham. https://doi.org/10.1007/978-3-319-33954-2_16

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-33954-2_16

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-33953-5

  • Online ISBN: 978-3-319-33954-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation