2
$\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$

2 Answers 2

0
$\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 13 at 12:25
  • $\begingroup$ You can make it $2^n T$, since you can compute the shortest path in a DAG in linear time $\endgroup$
    – Ggouvine
    Commented Jan 13 at 13:54
  • $\begingroup$ yeah, you are right, it can be more efficient for DAG. $\endgroup$ Commented Jan 14 at 8:56
0
$\begingroup$

This can be solved using a labeling algorithm. The procedure is very well explained here and here. I will let you read those sources for a better description of labeling algorithms than what I am able to provide here.

In the following I will show how this specific problem can be solved using a labeling algorithm, and assume knowledge of labeling algorithms in general.

Consider a label $L$ = (*, i, c, S)$, where:

  • $∗$ represents a pointer to the previous label,
  • $i$ is the current node,
  • $c$ is the accumulated cost, and
  • $S$ is a set containing the modes used. The initial label is characterized by the values $(null, s, 0, \emptyset)$. Here $null$ signifies the absence of a previous label, $s$ denotes the current node, $0$ is the accumulated cost, and $\emptyset$ is the empty set of modes used.

The resource extension functions when extending a label $L$ along arc $(i, j)$, using mode $k$, producing label $L^*$, are as follows: \begin{align} c(L^*) &= c(L) + cost(i,j,k) + \begin{cases} setup\_cost(k) \text{ if } k \notin s(L) \\ 0 \text{ otherwise} \end{cases} \\ S(L^*) &= S(L)\cup \{k\} \end{align}

Label $L_1$ dominates label $L_2$ iff: \begin{align} i(L_1) &= i(L_2) \\ c(L_1) &\leq c(L_2) - \sum_{k\in S(L_2)\backslash S(L_1)} setup\_cost(k) \end{align}

$\endgroup$
1
  • $\begingroup$ I had actually thought about how to use a labeling algorithm for this question before, but I couldn't quite figure it out. Thank you so much for your answer, it really helps me a lot! $\endgroup$ Commented Jan 14 at 8:52

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.