TY - JOUR

T1 - The covering path problem on a grid

AU - Zeng, Liwei

AU - Chopra, Sunil

AU - Smilowitz, Karen

N1 - Funding Information:
Financial support from Northwestern University Seed funding from the Office of Neighborhood and Community Relations at Northwestern University and the National Science Foundation [Grant CMMI-1727744] is gratefully acknowledged.
Funding Information:
Funding: Financial support from Northwestern University Seed funding from the Office of Neigh-borhood and Community Relations at Northwestern University and the National Science Foun-dation [Grant CMMI-1727744] is gratefully acknowledged. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2019.0901.
Publisher Copyright:
© 2019 INFORMS.

PY - 2019

Y1 - 2019

N2 - This paper introduces the covering path problem on a grid (CPPG) that finds the cost-minimizing path connecting a subset of points in a grid such that each point that needs to be covered is within a predetermined distance of a point from the chosen subset. We leverage the geometric properties of the grid graph, which captures the road network structure in many transportation problems, including our motivating setting of school bus routing. As defined in this paper, the CPPG is a biobjective optimization problem comprising one cost term related to path length and one cost term related to stop count. We develop a trade-off constraint, which quantifies the trade-off between path length and stop count and provides a lower bound for the biobjective optimization problem. We introduce simple construction techniques to provide feasible paths that match the lower bound within a constant factor. Importantly, this solution approach uses transformations of the general CPPG to either a discrete CPPG or continuous CPPG based on the value of the coverage radius. For both the discrete and continuous versions, we provide fast constantfactor approximations, thus solving the general CPPG.

AB - This paper introduces the covering path problem on a grid (CPPG) that finds the cost-minimizing path connecting a subset of points in a grid such that each point that needs to be covered is within a predetermined distance of a point from the chosen subset. We leverage the geometric properties of the grid graph, which captures the road network structure in many transportation problems, including our motivating setting of school bus routing. As defined in this paper, the CPPG is a biobjective optimization problem comprising one cost term related to path length and one cost term related to stop count. We develop a trade-off constraint, which quantifies the trade-off between path length and stop count and provides a lower bound for the biobjective optimization problem. We introduce simple construction techniques to provide feasible paths that match the lower bound within a constant factor. Importantly, this solution approach uses transformations of the general CPPG to either a discrete CPPG or continuous CPPG based on the value of the coverage radius. For both the discrete and continuous versions, we provide fast constantfactor approximations, thus solving the general CPPG.

KW - Covering path problem

KW - Grid optimization

KW - Location routing problem

KW - School bus routing

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

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

U2 - 10.1287/trsc.2019.0901

DO - 10.1287/trsc.2019.0901

M3 - Article

AN - SCOPUS:85077436844

SN - 0041-1655

VL - 53

SP - 1656

EP - 1672

JO - Transportation Science

JF - Transportation Science

IS - 6

ER -