1
$\begingroup$

I am working on a problem involving finding the shortest path in a Directed Acyclic Graph (DAG), where each edge's cost depends on multiple transportation modes, each with its own setup cost. I am looking for an algorithmic approach to solve this problem and would appreciate any guidance or suggestions.

Problem Description:

Consider a DAG with vertices $ V $ and directed edges $ E $. Each edge $ e \in E $ has a cost that depends on the transportation mode used. There are $ n $ different transportation modes available. The cost of using mode $ i $ on edge $ e $ is denoted as $ cost(e, i)$. Each transportation mode $i$ has an associated setup cost $ setup\_cost(i) $, which is incurred if the mode is used at least once in the path.

The objective is to find the shortest path from a designated start vertex $ s $ to an end vertex $ t $, considering the costs of edges based on the transportation modes and the setup costs of these modes.

Mathematical Model:

  • Let $ x_i $ be a binary variable that represents whether transportation mode $ i $ is used ($ x_i = 1 $) or not ($ x_i = 0$).
  • Let $ y_{e,i} $ be a binary variable that represents whether edge $ e $ is traversed using mode $ i $.

Objective:

Minimize the total cost, which includes the cost of traversing edges and the setup costs of the transportation modes:

$$ \text{Minimize} \sum_{e \in E, i=1}^{n} cost(e, i) \cdot y_{e,i} + \sum_{i=1}^{n} setup\_cost(i) \cdot x_i $$

Constraints:

  1. Each edge can be traversed using at most one transportation mode: $$ \sum_{i=1}^{n} y_{e,i} \leq 1 \quad \forall e \in E $$

  2. A transportation mode incurs a setup cost only if it is used: $$ y_{e,i} \leq x_i \quad \forall e \in E, \forall i=1,2,...,n $$

  3. Path constraints to ensure a valid path from $ s$ to $ t $ in the DAG.

Question:

Is there an existing algorithm or a known method that can efficiently solve this type of problem, especially considering the setup costs of different modes and the dependency of edge costs on these modes? Any pointers to algorithmic strategies or relevant literature would be highly appreciated.

$\endgroup$
3
  • $\begingroup$ How many modes of transportation are there? A small constant, like 5 or 10? Or a large number? $\endgroup$
    – D.W.
    Commented Jan 10 at 18:05
  • $\begingroup$ in a large-scale problem, the number of different types can potentially reach up to 30-40. $\endgroup$ Commented Jan 11 at 2:43
  • $\begingroup$ Are you interested in fast approximation algorithms? Or do you need to guarantee an optimal solution? For approximation, you could use randomized rounding and/or Lagrangian relaxation. $\endgroup$
    – Neal Young
    Commented Feb 18 at 13:31

1 Answer 1

1
$\begingroup$

This problem appears to be an NP problem, and here's a proof for it. Considering the presence of fixed setup costs in the problem, it brings to mind the uncapacitated facility location problem. Notably, when the shortest path in the problem is determined, but the modes for each arc in the path are still unknown, this scenario can be regarded as an uncapacitated facility location problem. This similarity allows us to perform a reduction from the facility location problem to the problem at hand.

$\endgroup$
3
  • $\begingroup$ Currently, the algorithm I've conceived maintains a complexity of$2^nT^2$, T represents the number of nodes in the directed acyclic graph. This involves solving the shortest path problem once for each setting of the modes. $\endgroup$ Commented Jan 10 at 12:06
  • $\begingroup$ By "an NP problem", do you mean that the problem is in NP, or that it is NP-hard? $\endgroup$
    – a3nm
    Commented Jan 16 at 8:27
  • 1
    $\begingroup$ I mean it's NP-hard. $\endgroup$ Commented Jan 16 at 11:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.