<p>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.</p>

CC BY-SA 4.0
2024-01-10T12:06:07.107Z
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.
Changxin Cao
CC BY-SA 4.0
2024-01-16T08:27:38.363Z
By "an NP problem", do you mean that the problem is in NP, or that it is NP-hard?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-01-16T11:29:07.027Z
I mean it's NP-hard.
Changxin Cao
CC BY-SA 4.0
2024-01-10T11:04:31.860Z
2024-01-10T11:04:31.860Z
Changxin Cao
<p>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.</p>
<p><strong>Problem Description:</strong></p>
<p>Consider a DAG with vertices <span class="math-container">$ V $</span> and directed edges <span class="math-container">$ E $</span>. Each edge <span class="math-container">$ e \in E $</span> has a cost that depends on the transportation mode used. There are <span class="math-container">$ n $</span> different transportation modes available. The cost of using mode <span class="math-container">$ i $</span> on edge <span class="math-container">$ e $</span> is denoted as <span class="math-container">$ cost(e, i)$</span>. Each transportation mode <span class="math-container">$i$</span> has an associated setup cost <span class="math-container">$ setup\_cost(i) $</span>, which is incurred if the mode is used at least once in the path.</p>
<p>The objective is to find the shortest path from a designated start vertex <span class="math-container">$ s $</span> to an end vertex <span class="math-container">$ t $</span>, considering the costs of edges based on the transportation modes and the setup costs of these modes.</p>
<p><strong>Mathematical Model:</strong></p>
<ul>
<li>Let <span class="math-container">$ x_i $</span> be a binary variable that represents whether transportation mode <span class="math-container">$ i $</span> is used (<span class="math-container">$ x_i = 1 $</span>) or not (<span class="math-container">$ x_i = 0$</span>).</li>
<li>Let <span class="math-container">$ y_{e,i} $</span> be a binary variable that represents whether edge <span class="math-container">$ e $</span> is traversed using mode <span class="math-container">$ i $</span>.</li>
</ul>
<p><strong>Objective:</strong></p>
<p>Minimize the total cost, which includes the cost of traversing edges and the setup costs of the transportation modes:</p>
<p><span class="math-container">$$
\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
$$</span></p>
<p><strong>Constraints:</strong></p>
<ol>
<li><p>Each edge can be traversed using at most one transportation mode:
<span class="math-container">$$
   \sum_{i=1}^{n} y_{e,i} \leq 1 \quad \forall e \in E
   $$</span></p>
</li>
<li><p>A transportation mode incurs a setup cost only if it is used:
<span class="math-container">$$
   y_{e,i} \leq x_i \quad \forall e \in E, \forall i=1,2,...,n
   $$</span></p>
</li>
<li><p>Path constraints to ensure a valid path from <span class="math-container">$ s$</span> to <span class="math-container">$ t $</span> in the DAG.</p>
</li>
</ol>
<p><strong>Question:</strong></p>
<p>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.</p>

CC BY-SA 4.0
2024-01-10T18:05:23.450Z
How many modes of transportation are there?  A small constant, like 5 or 10?  Or a large number?
D.W.
CC BY-SA 4.0
2024-01-11T02:43:30.537Z
in a large-scale problem, the number of different types can potentially reach up to 30-40.
Changxin Cao
CC BY-SA 4.0
2024-02-18T13:31:08.167Z
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.
Neal Young
<time-complexity><shortest-path><network-modeling>
Algorithm for Shortest Path in a DAG with Multiple Transportation Modes and Associated Setup Costs
Changxin Cao
# Algorithm for Shortest Path in a DAG with Multiple Transportation Modes and Associated Setup Costs

(Asked by: username_0 on 2024-01-10)

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.

**Tags:** time-complexity, shortest-path, network-modeling
> **Comments:**
> **username_1**: How many modes of transportation are there?  A small constant, like 5 or 10?  Or a large number?  
> **username_0**: in a large-scale problem, the number of different types can potentially reach up to 30-40.  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_0 on 2024-01-10. Score: 1

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.

> **Comments:**
> **username_0**: 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.  
> **username_3**: By "an NP problem", do you mean that the problem is in NP, or that it is NP-hard?  
> **username_0**: I mean it's NP-hard.  

---

