Data

Tools

Indexes

Applications

Experiments

Open Source Science

dddi

Interval-based Dynamic Discretization Discovery for solving the Continuous-Time Service Network Design Problem

https://github.com/mathgeekcoder/dddi

Science Score: 57.0%

This score indicates how likely this project is to be science-related based on various indicators:

  • ✓
    CITATION.cff file
    Found CITATION.cff file
  • ✓
    codemeta.json file
    Found codemeta.json file
  • ✓
    .zenodo.json file
    Found .zenodo.json file
  • ✓
    DOI references
    Found 4 DOI reference(s) in README
  • ○
    Academic publication links
  • ○
    Academic email domains
  • ○
    Institutional organization owner
  • ○
    JOSS paper metadata
  • ○
    Scientific vocabulary similarity
    Low similarity (7.7%) to scientific vocabulary
Last synced: 6 months ago · JSON representation ·

Repository

Interval-based Dynamic Discretization Discovery for solving the Continuous-Time Service Network Design Problem

Basic Info
  • Host: GitHub
  • Owner: mathgeekcoder
  • License: mit
  • Language: Python
  • Default Branch: main
  • Size: 15.4 MB
Statistics
  • Stars: 0
  • Watchers: 0
  • Forks: 0
  • Open Issues: 0
  • Releases: 0
Created 8 months ago · Last pushed 7 months ago
Metadata Files
Readme License Citation

README.md

Interval-based Dynamic Discretization Discovery for solving the Continuous-Time Service Network Design Problem

This repository contains some of the code and instances associated with the DDDI paper published in Transportation Science (2020).

Benchmark Results

The following results were produced on a desktop computer with an AMD Ryzen Threadripper PRO 5945WX 12-core CPU and 64 GB of RAM. Termination with 1% gap or after 1 hour.

The "Solve (s)" only includes time spent in Gurobi, whereas "Time (s)" includes everthing. As you can see the python code has relatively low overhead, but could be improved.

Gurobi 11

| Class | Gap (%) | Time (s) | Solve (s) | # its | Solved (%) | |-------:|--------:|---------:|----------:|------:|-----------:| | HC/HF | 0.96% | 707.23 | 699.24 | 17.3 | 89.3% | | HC/LF | 0.80% | 86.36 | 77.73 | 10.8 | 100.0% | | LC/HF | 0.53% | 0.04 | 0.01 | 0.5 | 100.0% | | LC/LF | 0.71% | 0.45 | 0.15 | 2.9 | 100.0% |

Gurobi 12

| Class | Gap (%) | Time (s) | Solve (s) | # its | Solved (%) | |-------:|--------:|---------:|----------:|------:|-----------:| | HC/HF | 1.04% | 576.91 | 568.36 | 17.8 | 92.7% | | HC/LF | 0.83% | 61.22 | 51.96 | 11.4 | 100.0% | | LC/HF | 0.55% | 0.04 | 0.01 | 0.5 | 100.0% | | LC/LF | 0.69% | 0.45 | 0.15 | 2.9 | 100.0% |

SND-RR (Gurobi 12)

| Class | Gap (%) | Time (s) | Solve (s) | # its | Solved (%) | |----------------:|--------:|---------:|----------:|------:|-----------:| | criticaltimes | 0.73% | 17.87 | 12.49 | 22.7 | 100.0% | | designatedpath | 0.80% | 26.17 | 11.13 | 31.6 | 100.0% | | hubandspoke | 0.62% | 6.73 | 3.88 | 17.1 | 100.0% |

Code Information

The original code is quite old, written during my PhD (2014 - 2017). Several changes have been made to update to Python 3.x and improve code quality. Also, I've recently added support for reading instances from SND-RR.

I never originally intended to release the code, so it has many hacks and is quite ugly! But for my own peace-of-mind I plan to slowly clean it up.

That said, it seems like there is ongoing research into DDD, and this code is still quite competitive with state-of-the-art. So it might be useful for comparisons.

Reference

If you use this, I'd love to hear about it. For academic usage, please cite this article.

Luke Marshall, Natashia Boland, Martin Savelsbergh, Mike Hewitt (2020) Interval-Based Dynamic Discretization Discovery for Solving the Continuous-Time Service Network Design Problem. Transportation Science 55(1):29-51. https://doi.org/10.1287/trsc.2020.0994

Owner

  • Name: Luke Marshall
  • Login: mathgeekcoder
  • Kind: user
  • Company: Microsoft Research

Citation (CITATION.cff) 

cff-version: 1.2.0
title: DDDI
message: >-
  Interval-based Dynamic Discretization Discovery for
  solving the Continuous-Time Service Network Design Problem
type: software
authors:
  - given-names: Luke
    family-names: Marshall
    email: mathgeekcoder@gmail.com
    orcid: 'https://orcid.org/0000-0003-0633-4004'
  - given-names: Natashia
    family-names: Boland
  - given-names: Martin
    family-names: Savelsbergh
  - given-names: Mike
    family-names: Hewitt
identifiers:
  - type: doi
    value: 10.1287/trsc.2020.0994
abstract: >-
  We introduce an effective and efficient iterative
  algorithm for solving the continuous-time service network
  design problem. The algorithm achieves its efficiency by
  carefully and dynamically refining partially time-expanded
  network models so that only a small number of small
  integer programs, defined over these networks, need to be
  solved. An extensive computational study shows that the
  algorithm performs well in practice, often using
  time-expanded network models with size much less than 1%
  (in terms of number of variables and constraints) of a
  full time-expanded network model. The algorithm is
  inspired by and has many similarities to the dynamic
  discretization discovery algorithm introduced in Boland et
  al. [Boland N, Hewitt M, Marshall L, Savelsbergh M (2017)
  The continuous-time service network design problem. Oper.
  Res. 65(5):1303–1321.], but generates smaller partially
  time-expanded models, produces high-quality solutions more
  quickly, and converges more quickly.
keywords:
  - service network design
  - time-expanded network
  - iterative refinement
  - dynamic discretization discovery
license: MIT

GitHub Events

Total
  • Push event: 2
Last Year
  • Push event: 2