A sampling-based strategy for distributing taxis in a road network for occupancy maximization (GIS Cup)

Kevin A. Buchin; Irina Kostitsyna; Bram Custers; Martijn A.C. Struijs

doi:10.1145/3347146.3363348

A sampling-based strategy for distributing taxis in a road network for occupancy maximization (GIS Cup)

Kevin A. Buchin, Irina Kostitsyna, Bram Custers, Martijn A.C. Struijs

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

2 Citations (Scopus)

1 Downloads (Pure)

Abstract

We present a weighted sampling strategy for distributing a system of taxi agents on a road network. We consider a setting, in which each agent operates independently, following a prescribed strategy based on historical data. Furthermore, customer requests appear dynamically and are assigned to the closest unoccupied taxi agent.

We demonstrate that in this setting a simple sampling strategy based on the spatial distribution of historical data performs well in minimizing the average time that agents are unoccupied. The strategy is evaluated on taxi trip data in Manhattan and compared to various, more complex strategies.

Original language	English
Title of host publication	27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2019
Editors	Farnoush Banaei-Kashani, Goce Trajcevski, Ralf Hartmut Guting, Lars Kulik, Shawn Newsam
Publisher	Association for Computing Machinery, Inc
Pages	616-619
Number of pages	4
ISBN (Electronic)	9781450369091
ISBN (Print)	978-1-4503-6909-1
DOIs	https://doi.org/10.1145/3347146.3363348
Publication status	Published - 5 Nov 2019
Event	27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems - Chicago, IL, United States Duration: 5 Nov 2019 → 8 Dec 2019 http://sigspatial2019.sigspatial.org/

Conference

Conference	27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
Abbreviated title	ACM SIGSPATIAL 2019
Country	United States
City	Chicago, IL
Period	5/11/19 → 8/12/19
Internet address	http://sigspatial2019.sigspatial.org/

Keywords

Dial-a-ride
Dynamic scheduling
GIS Cup
Multi-agent system
Taxi routing
Trajectories

Access to Document

10.1145/3347146.3363348

Fingerprint Dive into the research topics of 'A sampling-based strategy for distributing taxis in a road network for occupancy maximization (GIS Cup)'. Together they form a unique fingerprint.

Cite this

Buchin, K. A., Kostitsyna, I., Custers, B., & Struijs, M. A. C. (2019). A sampling-based strategy for distributing taxis in a road network for occupancy maximization (GIS Cup). In F. Banaei-Kashani, G. Trajcevski, R. H. Guting, L. Kulik, & S. Newsam (Eds.), 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2019 (pp. 616-619). Association for Computing Machinery, Inc. https://doi.org/10.1145/3347146.3363348

Buchin, Kevin A. ; Kostitsyna, Irina ; Custers, Bram ; Struijs, Martijn A.C. / A sampling-based strategy for distributing taxis in a road network for occupancy maximization (GIS Cup). 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2019. editor / Farnoush Banaei-Kashani ; Goce Trajcevski ; Ralf Hartmut Guting ; Lars Kulik ; Shawn Newsam. Association for Computing Machinery, Inc, 2019. pp. 616-619

@inproceedings{23847bde298848ca868ac68e87298f85,

title = "A sampling-based strategy for distributing taxis in a road network for occupancy maximization (GIS Cup)",

abstract = "We present a weighted sampling strategy for distributing a system of taxi agents on a road network. We consider a setting, in which each agent operates independently, following a prescribed strategy based on historical data. Furthermore, customer requests appear dynamically and are assigned to the closest unoccupied taxi agent.We demonstrate that in this setting a simple sampling strategy based on the spatial distribution of historical data performs well in minimizing the average time that agents are unoccupied. The strategy is evaluated on taxi trip data in Manhattan and compared to various, more complex strategies.",

keywords = "Dial-a-ride, Dynamic scheduling, GIS Cup, Multi-agent system, Taxi routing, Trajectories",

author = "Buchin, {Kevin A.} and Irina Kostitsyna and Bram Custers and Struijs, {Martijn A.C.}",

year = "2019",

month = nov,

day = "5",

doi = "10.1145/3347146.3363348",

language = "English",

isbn = "978-1-4503-6909-1",

pages = "616--619",

editor = "Farnoush Banaei-Kashani and Goce Trajcevski and Guting, {Ralf Hartmut} and Lars Kulik and Shawn Newsam",

booktitle = "27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2019",

publisher = "Association for Computing Machinery, Inc",

address = "United States",

note = "27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL 2019 ; Conference date: 05-11-2019 Through 08-12-2019",

url = "http://sigspatial2019.sigspatial.org/",

}

Buchin, KA , Kostitsyna, I , Custers, B & Struijs, MAC 2019, A sampling-based strategy for distributing taxis in a road network for occupancy maximization (GIS Cup). in F Banaei-Kashani, G Trajcevski, RH Guting, L Kulik & S Newsam (eds), 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2019. Association for Computing Machinery, Inc, pp. 616-619, 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Chicago, IL, United States, 5/11/19. https://doi.org/10.1145/3347146.3363348

A sampling-based strategy for distributing taxis in a road network for occupancy maximization (GIS Cup). / Buchin, Kevin A.; Kostitsyna, Irina ; Custers, Bram ; Struijs, Martijn A.C.

27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2019. ed. / Farnoush Banaei-Kashani; Goce Trajcevski; Ralf Hartmut Guting; Lars Kulik; Shawn Newsam. Association for Computing Machinery, Inc, 2019. p. 616-619.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - A sampling-based strategy for distributing taxis in a road network for occupancy maximization (GIS Cup)

AU - Buchin, Kevin A.

AU - Kostitsyna, Irina

AU - Custers, Bram

AU - Struijs, Martijn A.C.

PY - 2019/11/5

Y1 - 2019/11/5

N2 - We present a weighted sampling strategy for distributing a system of taxi agents on a road network. We consider a setting, in which each agent operates independently, following a prescribed strategy based on historical data. Furthermore, customer requests appear dynamically and are assigned to the closest unoccupied taxi agent.We demonstrate that in this setting a simple sampling strategy based on the spatial distribution of historical data performs well in minimizing the average time that agents are unoccupied. The strategy is evaluated on taxi trip data in Manhattan and compared to various, more complex strategies.

AB - We present a weighted sampling strategy for distributing a system of taxi agents on a road network. We consider a setting, in which each agent operates independently, following a prescribed strategy based on historical data. Furthermore, customer requests appear dynamically and are assigned to the closest unoccupied taxi agent.We demonstrate that in this setting a simple sampling strategy based on the spatial distribution of historical data performs well in minimizing the average time that agents are unoccupied. The strategy is evaluated on taxi trip data in Manhattan and compared to various, more complex strategies.

KW - Dial-a-ride

KW - Dynamic scheduling

KW - GIS Cup

KW - Multi-agent system

KW - Taxi routing

KW - Trajectories

UR - https://dl.acm.org/citation.cfm?doid=3347146.3363348

UR - http://www.scopus.com/inward/record.url?scp=85076959618&partnerID=8YFLogxK

U2 - 10.1145/3347146.3363348

DO - 10.1145/3347146.3363348

M3 - Conference contribution

SN - 978-1-4503-6909-1

SP - 616

EP - 619

BT - 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2019

A2 - Banaei-Kashani, Farnoush

A2 - Trajcevski, Goce

A2 - Guting, Ralf Hartmut

A2 - Kulik, Lars

A2 - Newsam, Shawn

PB - Association for Computing Machinery, Inc

T2 - 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

Y2 - 5 November 2019 through 8 December 2019

ER -

Buchin KA , Kostitsyna I , Custers B , Struijs MAC. A sampling-based strategy for distributing taxis in a road network for occupancy maximization (GIS Cup). In Banaei-Kashani F, Trajcevski G, Guting RH, Kulik L, Newsam S, editors, 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2019. Association for Computing Machinery, Inc. 2019. p. 616-619 https://doi.org/10.1145/3347146.3363348