The Covering Path Problem on a Grid

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. The authors leverage the geometric properties of the grid graph, which captures the road network structure in many transportation problems, including the authors' 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. The authors 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. The authors 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, the authors provide fast constant-factor approximations, thus solving the general CPPG.

  • Record URL:
  • Availability:
  • Supplemental Notes:
    • Abstracts reprinted with permission of INFORMS (Institute for Operations Research and the Management Sciences,
  • Authors:
    • Zeng, Liwei
    • Chopra, Sunil
    • Smilowitz, Karen
  • Publication Date: 2019-11


  • English

Media Info

  • Media Type: Web
  • Features: Figures; References; Tables;
  • Pagination: pp 1656-1672
  • Serial:

Subject/Index Terms

Filing Info

  • Accession Number: 01723786
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Nov 27 2019 10:36AM