Algorithm for Shortest Path in a DAG with Multiple Transportation Modes and Associated Setup Costs

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.

• How many modes of transportation are there? A small constant, like 5 or 10? Or a large number?
– D.W.
Commented Jan 10 at 18:05
• in a large-scale problem, the number of different types can potentially reach up to 30-40. Commented Jan 11 at 2:43
• 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. Commented Feb 18 at 13:31

• 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. Commented Jan 10 at 12:06