SUPR
Towards Real World Applicability: Developing Neural Solvers for More Realistic Routing Problems
Dnr:

NAISS 2024/5-642

Type:

NAISS Medium Compute

Principal Investigator:

Balázs Adam Kulcsár

Affiliation:

Chalmers tekniska högskola

Start Date:

2024-12-20

End Date:

2026-01-01

Primary Classification:

20105: Transport Systems and Logistics

Webpage:

Allocation

Abstract

In recent years, machine-learning-based solvers for routing problems have become more and more popular. This is due to the NP-hard nature of many such problems which imposes a computationally prohibitive runtime on traditional solvers in practice. Therefore, a need for strong, heuristic-based solvers arises. Such solvers can be developed using machine-learning techniques. However, so far, the literature developing neural-network-based solvers has a strong focus on symmetric routing problems. The problems have the assumption that distances between nodes of a routing problem instance can simply be derived from the distribution of these nodes in a Euclidean space. This assumption does generally not hold in reality, where distances between cities are often highly asymmetric (e.g., due to one-way streets). This effect becomes even stronger, when the objective function focuses on time (traffic jams often only affect one direction) or energy (travelling from a lower altitude to a higher altitude requires more energy than the other way around) instead of only travelled distances. Therefore, we aim to develop neural solvers capable of efficiently and effectively solving asymmetric routing problems.