For vehicle routing problems, strong dual bounds on the optimal value are needed to develop scalable exact algorithms as well as to evaluate the performance of heuristics. In this work, we propose an iterative algorithm to compute dual bounds motivated by connections between decision diagrams and dynamic programming models used for pricing in branch-and-cut-and-price algorithms. We apply techniques from the decision diagram literature to generate and strengthen novel route relaxations for obtaining dual bounds without using column generation. Our approach is generic and can be applied to various vehicle routing problems in which corresponding dynamic programming models are available. We apply our framework to the traveling salesman with drone problem and show that it produces dual bounds competitive to those from the state of the art. Applied to larger problem instances in which the state-of-the-art approach does not scale, our method outperforms other bounding techniques from the literature.
Funding: This work was supported by the National Science Foundation [Grant 1918102] and the Office of Naval Research [Grants N00014-18-1-2129 and N00014-21-1-2240].
Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2021.0170 .
more » « less- Award ID(s):
- 1918102
- PAR ID:
- 10484633
- Publisher / Repository:
- INFORMS
- Date Published:
- Journal Name:
- Transportation Science
- ISSN:
- 0041-1655
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
Public-transit systems face a number of operational challenges: (a) changing ridership patterns requiring optimization of fixed line services, (b) optimizing vehicle-to-trip assignments to reduce maintenance and operation codes, and (c) ensuring equitable and fair coverage to areas with low ridership. Optimizing these objectives presents a hard computational problem due to the size and complexity of the decision space. State-of-the-art methods formulate these problems as variants of the vehicle routing problem and use data-driven heuristics for optimizing the procedures. However, the evaluation and training of these algorithms require large datasets that provide realistic coverage of various operational uncertainties. This paper presents a dynamic simulation platform, called Transit-Gym, that can bridge this gap by providing the ability to simulate scenarios, focusing on variation of demand models, variations of route networks, and variations of vehicle-to-trip assignments. The central contribution of this work is a domain-specific language and associated experimentation tool-chain and infrastructure to enable subject-matter experts to intuitively specify, simulate, and analyze large-scale transit scenarios and their parametric variations. Of particular significance is an integrated microscopic energy consumption model that also helps to analyze the energy cost of various transit decisions made by the transportation agency of a city.more » « less
-
null (Ed.)Public-transit systems face a number of operational challenges: (a) changing ridership patterns requiring optimization of fixed line services, (b) optimizing vehicle-to-trip assignments to reduce maintenance and operation codes, and (c) ensuring equitable and fair coverage to areas with low ridership. Optimizing these objectives presents a hard computational problem due to the size and complexity of the decision space. State-of-the-art methods formulate these problems as variants of the vehicle routing problem and use data-driven heuristics for optimizing the procedures. However, the evaluation and training of these algorithms require large datasets that provide realistic coverage of various operational uncertainties. This paper presents a dynamic simulation platform, called Transit-Gym, that can bridge this gap by providing the ability to simulate scenarios, focusing on variation of demand models, variations of route networks, and variations of vehicle-to-trip assignments. The central contribution of this work is a domain-specific language and associated experimentation tool-chain and infrastructure to enable subject-matter experts to intuitively specify, simulate, and analyze large-scale transit scenarios and their parametric variations. Of particular significance is an integrated microscopic energy consumption model that also helps to analyze the energy cost of various transit decisions made by the transportation agency of a city.more » « less
-
null (Ed.)Public-transit systems face a number of operational challenges: (a) changing ridership patterns requiring optimization of fixed line services, (b) optimizing vehicle-to-trip assignments to reduce maintenance and operation codes, and (c) ensuring equitable and fair coverage to areas with low ridership. Optimizing these objectives presents a hard computational problem due to the size and complexity of the decision space. State-of-the-art methods formulate these problems as variants of the vehicle routing problem and use data-driven heuristics for optimizing the procedures. However, the evaluation and training of these algorithms require large datasets that provide realistic coverage of various operational uncertainties. This paper presents a dynamic simulation platform, called \textsc{Transit-Gym}, that can bridge this gap by providing the ability to simulate scenarios, focusing on variation of demand models, variations of route networks, and variations of vehicle-to-trip assignments. The central contribution of this work is a domain-specific language and associated experimentation tool-chain and infrastructure to enable subject-matter experts to intuitively specify, simulate, and analyze large-scale transit scenarios and their parametric variations. Of particular significance is an integrated microscopic energy consumption model that also helps to analyze the energy cost of various transit decisions made by the transportation agency of a city.more » « less
-
Sparse decision tree optimization has been one of the most fundamental problems in AI since its inception and is a challenge at the core of interpretable machine learning. Sparse decision tree optimization is computationally hard, and despite steady effort since the 1960's, breakthroughs have been made on the problem only within the past few years, primarily on the problem of finding optimal sparse decision trees. However, current state-of-the-art algorithms often require impractical amounts of computation time and memory to find optimal or near-optimal trees for some real-world datasets, particularly those having several continuous-valued features. Given that the search spaces of these decision tree optimization problems are massive, can we practically hope to find a sparse decision tree that competes in accuracy with a black box machine learning model? We address this problem via smart guessing strategies that can be applied to any optimal branch-and-bound-based decision tree algorithm. The guesses come from knowledge gleaned from black box models. We show that by using these guesses, we can reduce the run time by multiple orders of magnitude while providing bounds on how far the resulting trees can deviate from the black box's accuracy and expressive power. Our approach enables guesses about how to bin continuous features, the size of the tree, and lower bounds on the error for the optimal decision tree. Our experiments show that in many cases we can rapidly construct sparse decision trees that match the accuracy of black box models. To summarize: when you are having trouble optimizing, just guess.more » « less
-
We propose data-driven one-pass streaming algorithms for estimating the number of triangles and four cycles, two fundamental problems in graph analytics that are widely studied in the graph data stream literature. Recently, Hsu et al. (2019a) and Jiang et al. (2020) applied machine learning techniques in other data stream problems, using a trained oracle that can predict certain properties of the stream elements to improve on prior “classical” algorithms that did not use oracles. In this paper, we explore the power of a “heavy edge” oracle in multiple graph edge streaming models. In the adjacency list model, we present a one-pass triangle counting algorithm improving upon the previous space upper bounds without such an oracle. In the arbitrary order model, we present algorithms for both triangle and four cycle estimation with fewer passes and the same space complexity as in previous algorithms, and we show several of these bounds are optimal. We analyze our algorithms under several noise models, showing that the algorithms perform well even when the oracle errs. Our methodology expands upon prior work on “classical” streaming algorithms, as previous multi-pass and random order streaming algorithms can be seen as special cases of our algorithms, where the first pass or random order was used to implement the heavy edge oracle. Lastly, our experiments demonstrate advantages of the proposed method compared to state-of-the-art streaming algorithms.more » « less