Approximation Algorithms for Route Planning with Nonlinear Objectives
Authors: Ger Yang, Evdokia Nikolova
AAAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experimental Evaluations We tested our algorithm on a grid graph and a real transportation network. The algorithm is implemented in C++. Experiments are run on an Intel Core i7 1.7 GHz (I7-4650U) processor. Due to memory constraints, the table {Πi v|v V } is implemented as a binary search tree, where query, insertion, and update operations can be done in time TΠ = O(log(n|Γ|)). Memory turns out to be the limiting factor for the problem size and accuracy available to our experiments. In this section, memory usage refers to the total number of sub-paths maintained in the table {Πi v|v V }. We tested the deadline problem with a hop constraint on a 5 5 grid graph, 10 10 grid graph, and the Anaheim network (416 vertices, 914 edges) from the real world data set (Bar-Gera 2002). The grid graphs are bi-directional, and the mean and the variance for each edge are randomly generated from [0.1, 5]. We routed from node (0, 0) to node (4, 4) on the 5 5 grid, and from (1, 1) to (8, 8) on the 10 10 grid. The Anaheim dataset provides the mean travel time. The variance for each edge is randomly generated from 0 to the mean. The source and destination are randomly chosen. Table 1 summarizes the results on the datasets, which are the average of 20 experiments. |
| Researcher Affiliation | Academia | Ger Yang Electrical and Computer Engineering University of Texas at Austin geryang@utexas.edu Evdokia Nikolova Electrical and Computer Engineering University of Texas at Austin nikolova@austin.utexas.edu |
| Pseudocode | Yes | Algorithm 1 Nonlinear Objective Shortest Path with Hop-constraint |
| Open Source Code | No | The paper does not contain any statements about making its source code publicly available, nor does it provide links to a code repository for the methodology described. |
| Open Datasets | Yes | We tested the deadline problem with a hop constraint on a 5 5 grid graph, 10 10 grid graph, and the Anaheim network (416 vertices, 914 edges) from the real world data set (Bar-Gera 2002). |
| Dataset Splits | No | The paper describes the datasets used (grid graphs, Anaheim network) and specific routing tasks (e.g., 'from node (0,0) to node (4,4)'), but it does not provide any specific details regarding training, validation, or test splits for these datasets. |
| Hardware Specification | Yes | Experiments are run on an Intel Core i7 1.7 GHz (I7-4650U) processor. |
| Software Dependencies | No | The paper states 'The algorithm is implemented in C++', but it does not provide specific version numbers for the programming language or any ancillary software libraries or solvers used in the experiments. |
| Experiment Setup | Yes | The grid graphs are bi-directional, and the mean and the variance for each edge are randomly generated from [0.1, 5]. ... The variance for each edge is randomly generated from 0 to the mean. The source and destination are randomly chosen. |