The Covering Path Problem on a Grid

Liwei Zeng (), Sunil Chopra () and Karen Smilowitz ()
Additional contact information
Liwei Zeng: Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, Illinois 60208
Sunil Chopra: Kellogg School of Management, Northwestern University, Evanston, Illinois 60208
Karen Smilowitz: Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, Illinois 60208

Transportation Science, 2019, vol. 53, issue 6, 1656-1672

Abstract: 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 constant-factor approximations, thus solving the general CPPG.

Keywords: covering path problem; grid optimization; school bus routing; location routing problem (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/trsc.2019.0901 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:53:y:2019:i:6:p:1656-1672

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().