Skip to main content

2019 | OriginalPaper | Buchkapitel

Real-Time Route Planning and Online Order Dispatch for Bus-Booking Platforms

verfasst von : Hao Zhou, Yucen Gao, Xiaofeng Gao, Guihai Chen

Erschienen in: Database Systems for Advanced Applications

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

To cater to the high travel demands in Beijing Capital International Airport during 23:00–2:00, Beijing Traffic Management Bureau (BTMB) intends to develop a new service named bus-booking platforms. Compared to traditional airport shuttle buses, bus-booking platforms can conduct flexible route planning and online order dispatch while provide much lower price than the common car-hailing platform, e.g., Didi Chuxing. We conduct the real-time route planning by solving the standard Capacitated Vehicles Routing Problem based on the order prediction. In addition, we focus on the design of the online order dispatch algorithm for bus-booking platforms, which is novel and extremely different from the traditional taxi order dispatch in car-hailing platforms. When an order is dispatched, multiple influence factors will be considered simultaneously, such as the bus capacity, the balanced distribution of the accepted orders and the travel time of passengers, all of which aim to provide a better user experience. Moreover, we prove that our online algorithms can achieve the tight competitive ratio in this paper, where the competitive ratio is the ratio between the solution of an online algorithm and the offline optimal solution.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Anhänge
Nur mit Berechtigung zugänglich
Literatur
2.
Zurück zum Zitat Allahviranloo, M., Chow, J.Y., Recker, W.W.: Selective vehicle routing problems under uncertainty without recourse. Transp. Res. Part E Logist. Transp. Rev. 62, 68–88 (2014)CrossRef Allahviranloo, M., Chow, J.Y., Recker, W.W.: Selective vehicle routing problems under uncertainty without recourse. Transp. Res. Part E Logist. Transp. Rev. 62, 68–88 (2014)CrossRef
3.
Zurück zum Zitat Cáceres-Cruz, J., Arias, P., Guimarans, D., Riera, D., Juan, A.A.: Rich vehicle routing problem: survey. ACM Comput. Surv. 47(2), 32:1–32:28 (2014)CrossRef Cáceres-Cruz, J., Arias, P., Guimarans, D., Riera, D., Juan, A.A.: Rich vehicle routing problem: survey. ACM Comput. Surv. 47(2), 32:1–32:28 (2014)CrossRef
4.
Zurück zum Zitat Lee, D.-H., Wang, H., Cheu, R.L., Teo, S.H.: Taxi dispatch system based on current demands and real-time traffic conditions. Transp. Res. Rec. J. Transp. Res. Board 1882, 193–200 (2004)CrossRef Lee, D.-H., Wang, H., Cheu, R.L., Teo, S.H.: Taxi dispatch system based on current demands and real-time traffic conditions. Transp. Res. Rec. J. Transp. Res. Board 1882, 193–200 (2004)CrossRef
5.
Zurück zum Zitat Liao, Z.: Real-time taxi dispatching using global positioning systems. Commun. ACM (CACM) 46(5), 81–83 (2003)CrossRef Liao, Z.: Real-time taxi dispatching using global positioning systems. Commun. ACM (CACM) 46(5), 81–83 (2003)CrossRef
6.
Zurück zum Zitat Moreira-Matias, L., Gama, J., Ferreira, M., Mendes-Moreira, J., Damas, L.: Predicting taxi-passenger demand using streaming data. IEEE Trans. Intell. Transp. Syst. (TITS) 14(3), 1393–1402 (2013)CrossRef Moreira-Matias, L., Gama, J., Ferreira, M., Mendes-Moreira, J., Damas, L.: Predicting taxi-passenger demand using streaming data. IEEE Trans. Intell. Transp. Syst. (TITS) 14(3), 1393–1402 (2013)CrossRef
7.
Zurück zum Zitat Munkres, J.: Algorithms for the assignment and transportation problems. J. Soc. Ind. Appl. Math. 5(1), 32–38 (1957)MathSciNetCrossRef Munkres, J.: Algorithms for the assignment and transportation problems. J. Soc. Ind. Appl. Math. 5(1), 32–38 (1957)MathSciNetCrossRef
8.
Zurück zum Zitat Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs (1982)MATH Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs (1982)MATH
9.
Zurück zum Zitat Ralphs, T.K., Kopman, L., Pulleyblank, W.R., Trotter, L.E.: On the capacitated vehicle routing problem. Math. Program. 94(2–3), 343–359 (2003)MathSciNetCrossRef Ralphs, T.K., Kopman, L., Pulleyblank, W.R., Trotter, L.E.: On the capacitated vehicle routing problem. Math. Program. 94(2–3), 343–359 (2003)MathSciNetCrossRef
10.
Zurück zum Zitat Seow, K.T., Dang, N.H., Lee, D.: A collaborative multiagent taxi-dispatch system. IEEE Trans. Autom. Sci. Eng. (TASAE) 7(3), 607–616 (2010)CrossRef Seow, K.T., Dang, N.H., Lee, D.: A collaborative multiagent taxi-dispatch system. IEEE Trans. Autom. Sci. Eng. (TASAE) 7(3), 607–616 (2010)CrossRef
11.
Zurück zum Zitat Tong, Y., et al.: The simpler the better: a unified approach to predicting original taxi demands based on large-scale online platforms. In: ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD), pp. 1653–1662 (2017) Tong, Y., et al.: The simpler the better: a unified approach to predicting original taxi demands based on large-scale online platforms. In: ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD), pp. 1653–1662 (2017)
12.
Zurück zum Zitat Xu, Z., et al.: Large-scale order dispatch in on-demand ride-hailing platforms: a learning and planning approach. In: ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD), pp. 905–913 (2018) Xu, Z., et al.: Large-scale order dispatch in on-demand ride-hailing platforms: a learning and planning approach. In: ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD), pp. 905–913 (2018)
13.
Zurück zum Zitat Zhang, L., et al.: A taxi order dispatch model based on combinatorial optimization. In: ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD), pp. 2151–2159 (2017) Zhang, L., et al.: A taxi order dispatch model based on combinatorial optimization. In: ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD), pp. 2151–2159 (2017)
14.
Zurück zum Zitat Zhang, R., Pavone, M.: Control of robotic mobility-on-demand systems: a queueing-theoretical perspective. Int. J. Robot. Res. 35(1–3), 186–203 (2016)CrossRef Zhang, R., Pavone, M.: Control of robotic mobility-on-demand systems: a queueing-theoretical perspective. Int. J. Robot. Res. 35(1–3), 186–203 (2016)CrossRef
Metadaten
Titel
Real-Time Route Planning and Online Order Dispatch for Bus-Booking Platforms
verfasst von
Hao Zhou
Yucen Gao
Xiaofeng Gao
Guihai Chen
Copyright-Jahr
2019
DOI
https://doi.org/10.1007/978-3-030-18579-4_44