<figure><img src="image_1.png" /></figure>

HAL
open science

# A MILP Framework to Solve the Sustainable System Optimum with Link MFD Functions

Niloofar Shakoori, Giovanni de Nunzio, Ludovic Leclercq

► To cite this version:

Niloofar Shakoori, Giovanni de Nunzio, Ludovic Leclercq. A MILP Framework to Solve the Sustainable System Optimum with Link MFD Functions. 4th Symposium on Management of Future Motorway and Urban Traffic Systems (MFTS), Technische Universität Dresden, Nov 2022, Dresden, Germany. pp.89-98, 10.25368/2023.102 . hal-04147045v2

HAL Id: hal-04147045

https://ifp.hal.science/hal-04147045v2

Submitted on 30 Jun 2023

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
# A MILP Framework to Solve the Sustainable System Optimum with Link MFD Functions

Niloofar Shakoori<fnref n="1" />, Giovanni De Nunzio<fnref n="1" />, Ludovic Leclercq<fnref n="2" />

## Abstract

Given the increasing consciousness toward the environmental footprint of mobility, accommodating environmental objectives in existing transport planning strategies is imperative for research and practice. In this paper, we use the link macroscopic fundamental diagram (MFD) model to develop optimal routing strategies that minimize total system emissions (TSE) in multiple origin-destination (OD) networks. Piecewise linear (PWL) functions are used to approximate MFD for individual links, and to define link-level emissions. Dynamic network constraints, non-vehicle holding constraints, and convex formulations of the PWL functions are considered. Thus, the system-optimum dynamic traffic assignment (SO-DTA) problem with environmental objectives is formulated as a mixed integer linear program (MILP). Finally, on a synthetic network, numerical examples demonstrate the performance of the proposed framework.

**Keywords:** traffic assignment, system optimum, macroscopic fundamental diagram, emissions

## 1 Introduction

Congestion in transportation networks and its eminent environmental effects are becoming imperative issues in recent times. In this regard, optimal routing strategies are emerging as viable solutions to improve transportation network management and tackle these issues. Environmental objectives should be considered at the network level. Sustainable System Optimum (SSO) is thus a special case of the SO-DTA [She84] where the minimization process targets the emissions instead of the total travel time.

To solve the SSO while considering traffic dynamics, we employ discrete-time analytical SO-DTA models that are mostly formulated as linear programming (LP) and mixed integer linear programming (MILP) problems (e.g. [Zil00; Azi12; Lon18]). Based on objectives, the existing SO-DTA models can be categorized into two main groups: minimizing total

<footnote n="1">¹ IFP Energies nouvelles, Rueil-Malmaison, France,</footnote>

<footnote n="2">² LICIT-ECO7, ENTPE, Gustave Eiffel University, Lyon, France</footnote>
system travel time (TSTT) (e.g. [Gha95; Zil00; Lon19]), and minimizing total system emissions (TSE) (e.g. [Azi12; Lon18]). Throughout the literature, it is evident that most existing SO-DTA models are concerned with the TSTT. Built upon linear and convex functions, such objectives have advantages such as being computationally efficient for reasonably sized networks. On the other hand, few studies have attempted to address the TSE in the SO-DTA model. Their main limitations reside in the computational performance due to the nonlinear and non-convex objective functions, as well as in the contextual applicability due to solely examining simplified single OD networks.

This study extends the MILP framework for solving TSTT by [Sha22] to address the TSE on multiple OD networks. We adopt the PWL link-MFD functions to describe link-level traffic dynamics. So, each link can be represented by a single cell characterized by its density. The link-MFD characterizes the effect of traffic control and the different states that a link between two intersections can encounter. From the PWL link MFDs, we further derive the PWL link emissions to tackle the non-linear TSE objective function. Additionally, we investigate the challenges for TSE optimization and study multiple alternatives to improve the computational efficiency of the proposed framework such as reducing the dimensionality of the problem and path selection strategies. The remainder of this paper is organized as follows. Section 2 presents the methodological framework. Section 3 provides a case study, numerical results, and discussions.

<figure><img src="image_2.png" /><figcaption>**Figure 1:** Link-level MFD, triangular FD approximation, and its PWL MFD counterpart.</figcaption></figure>
<table><caption>Table 1: Nomenclature.</caption><thead><tr><th>Notation</th><th>Description</th></tr></thead><tbody><tr><td>T</td><td>Set of discrete time intervals</td></tr><tr><td>Δt</td><td>Time interval duration</td></tr><tr><td>C<sub>R</sub></td><td>Set of origin links</td></tr><tr><td>C<sub>S</sub></td><td>Set of destination links</td></tr><tr><td>C</td><td>Set of links except for the destination links</td></tr><tr><td>Q<sup>t</sup><sub>i</sub></td><td>The maximum flow that can get into or out of link i at time interval t</td></tr><tr><td>l<sub>i</sub></td><td>Length of link i</td></tr><tr><td>d<sup>O,D,t</sup></td><td>Demand from origin O to destination D at interval t</td></tr><tr><td>x<sup>O,D,t</sup><sub>i</sub></td><td>Number of vehicles in link i during time t oriented from origin O headed to destination D</td></tr><tr><td>y<sup>O,D,t</sup><sub>i,j</sub></td><td>Number of vehicles moving from link i to link j during time t from origin O to destination D</td></tr><tr><td>k<sup>O,D,t</sup><sub>i</sub></td><td>OD Segregated density of link i at time t</td></tr><tr><td>k<sup>t</sup><sub>i</sub></td><td>Aggregated density of link i at time t</td></tr><tr><td>Γ(i)</td><td>Set of successor links of link i</td></tr><tr><td>Γ(i)<sup>-1</sup></td><td>Set of predecessor links of link i</td></tr><tr><td>Γ(i)<sup>O,D</sup></td><td>Set of successor links of link i on the paths from origin O to destination D</td></tr><tr><td>Γ(i)<sup>-1,O,D</sup></td><td>Set of predecessor links of link i on the paths from origin O to destination D</td></tr><tr><td>D(k<sup>t</sup><sub>i</sub>)</td><td>Aggregated demand in link i during time t as a function of density</td></tr><tr><td>D(k<sup>O,D,t</sup><sub>i</sub>)</td><td>Segregated demand in link i from origin O to destination D during time t as a function of density</td></tr><tr><td>S(k<sup>t</sup><sub>i</sub>)</td><td>Aggregated supply at cell i during time t as a function of density</td></tr></tbody></table>

## 2 Methodology

In this section, we present a MILP framework for modeling a link-based TSE-SO-DTA. Table 1 resumes the adopted nomenclature.

### 2.1 Piecewise Linear Link Macroscopic Fundamental Diagram

As depicted in Figure 1, we approximate the link MFDs by PWL functions. Accordingly, the PWL demand (branches *I*, *II*, and *III*, and *VIII*) and supply functions (branches *VII*, *IV*, *V*, *VI*) can be defined by their breakpoints by employing a convex combination formulation and a set of variables, known as the special ordered sets of type 2 (SOS2) in which at most two variables can be positive, and if two are positive they must be consecutive [Keh04; Bea69].
Given the B breakpoints on the PWL demand function as $(k_{i,b}^t, F_{i,b}^t)$ for $b \in \{1, \dots, B\}$, for each link $i$ at time $t$ we can write:

$$k_i^t = \sum_{b=1}^{B} k_{i,b}^t \times \lambda_{i,b}^t, \qquad (1)$$

$$D(k_i^t) = \sum_{b=1}^{B} F_{i,b}^t \times \lambda_{i,b}^t, \qquad (2)$$

$$\text{where } \sum_{b=1}^{B} \lambda_{i,b}^t = 1, \qquad (3)$$

$$\lambda_{i,b}^t \ge 0 \quad \forall b \in \{1, \dots, B\}, \qquad (4)$$

$$\lambda_{i,b}^t \quad b \in \{1, \dots, B\} \text{ is SOS2.} \qquad (5)$$

$D(k_i^t)$ is the aggregated demand at link $i$ during time $t$. To determine the OD segregated demand at link $i$ during time $t$, one can use the aggregated demand and derive it in proportion to the OD segregated densities.

## 2.2 Link MFD-based Dynamic Network Constraints

Analytical description of the traffic model in link MFD-based TSE-SO-DTA problem requires introducing a set of constraints to the MILP framework. This includes the initial state of the network, the mass flow conservation, flow propagation relations, and non-vehicle holding (NVH) conditions. We adopt the same set of discrete-time MILP constraints introduced by [Sha22]:

$$x_i^{O,D,0} = 0, y_{i,j}^{O,D,0} = 0 \qquad \forall i \in C, \forall j \in C, \forall O \in C_R, D \in C_S, \qquad (6)$$

$$x_i^{O,D,t} \ge 0, y_{i,j}^{O,D,t} \ge 0 \qquad \forall i \in C \cup C_s, \forall O \in C_R, D \in C_S, t \in T, \qquad (7)$$

$$x_i^{O,D,t} - x_i^{O,D,t-1} + \sum_{j \in \Gamma^{O,D}(i)} y_{i,j}^{O,D,t-1} = d^{O,D,t-1} \qquad \forall i \in C_R, O \in C_R, D \in C_S, \forall t \in T, \qquad (8)$$

$$x_i^{O,D,t} - x_i^{O,D,t-1} - \sum_{k \in \Gamma^{-1,O,D}(i)} y_{k,i}^{O,D,t-1} + \sum_{j \in \Gamma^{O,D}(i)} y_{i,j}^{O,D,t-1} = 0 \qquad \forall i \in C \setminus C_R, O \in C_R, D \in C_S, t \in T, \qquad (9)$$

$$\sum_{O,D} \sum_{j \in \Gamma^{O,D}(i)} y_{i,j}^{O,D,t} \le D(k_i^t) \times \Delta t, \qquad O \in C_R, D \in C_S, \qquad (10)$$

$$\sum_{O,D} \sum_{k \in \Gamma^{-1,O,D}(j)} y_{k,j}^{O,D,t} \le S(k_j^t) \times \Delta t, \qquad O \in C_R, D \in C_S, \forall j \in \Gamma(i), \qquad (11)$$
$$ \sum_{j \in \Gamma^{O,D}(i)} y_{i,j}^{O,D,t} \leq D(k_i^{O,D,t}) \quad \forall t \in T, O \in C_R, D \in C_S, \quad (12) $$

$$ -\left[ \sum_{a=1}^{m_i} \theta_i^a(t) \right] M \leq \sum_{O,D} \sum_{j \in \Gamma^{O,D}(i)} y_{i,j}^{O,D,t} - D(k_i^t) \times \Delta t \quad \forall i \in C, \forall t \in T, \quad (13) $$

$$ -\left[ \sum_{a=1}^{m_i} \sigma_a^g - \sum_{a=1}^{m_i} (2\sigma_a^g - 1)\theta_i^a(t) \right] M \leq \sum_{O,D} \sum_{k \in \Gamma^{-1,O,D}(j_g)} y_{k,j_g}^{O,D,t} - S(k_{j_g}^t) \times \Delta t \quad \forall i \in C, t \in T, g \in G_i, \quad (14) $$

$$ \sum_{a=1}^{m_i} 2^a \theta_i^a(t) \leq 2|\Gamma(i)| \quad \forall i \in C, \forall t \in T, \quad (15) $$

$$ \theta_i^a(t) \in \{0,1\}, a = 1, \dots, m_i \quad \forall i \in C, \forall t \in T, \quad (16) $$

where M is a very large positive value, $G_i = \{1, 2, \dots, |\Gamma(i)|\}$ is an index set for link i's successor links, $j_g$ is the g-th link in $\Gamma(i)$, $m_i = \argmin_m \{2^{m+1} \ge 2 + 2 \times |\Gamma(i)|\}$, and $\sigma_a^g$ is 0 or 1, such that $\sum_{a=1}^{m_i} 2^{a-1} \times \sigma_a^g = g$.

The initial state of the network is captured in Equation (6). Equation (7) ensures the non-negativity of the variables. The link mass conservation is guaranteed by Equations (8)–(9). Equations (10)–(12) represent the flow propagation constraints. Equations (13)–(16) ensure the NVH conditions.

## 2.3 Link MFD-based SO-DTA Models in Terms of Total System Emission (TSE)

In a TSE-SO-DTA we are seeking to minimize the network-level pollutant emission which can be obtained by the sum of links' emissions during the simulation period. The objective function then reads:

$$ \min_{x_i^t} TSE = \sum_{i \in C} \sum_{t \in T} E_i^t. \quad (17) $$

$E_i^t$ represents link emission and can be calculated as the product of (i) total traveled distance (TTD) of all vehicles on the link and (ii) emission factor (EF) modeled as a function of mean speed according to the COPERT model [EEA22]. Therefore:

$$ E_i^t = TTD \times EF = \Delta T \times x_i^t \times V(x_i^t) \times EF(V(x_i^t)). \quad (18) $$

A polynomial regression model is used to compute the CO₂ emission factor as a function of speed for an aggregated vehicle representing the entire French vehicle fleet (fleet composition data in [Cit17]):

$$ EF(V(x_i^t)) = p_4 V(x_i)^4 + p_3 V(x_i)^3 + p_2 V(x_i)^2 + p_1 V(x_i) + p_0. \quad (19) $$

The coefficients of the regression model (i.e. $p_4, p_3, p_2, p_1$, and $p_0$) were estimated from speed-emission data.
For any given density, considering traffic demand constant during each time step, the mean speed and the emission factor can be calculated from Equation (19). This implies that for every breakpoint on the PWL link MFD, knowing the mean speed (speed = $\frac{flow}{density}$), the corresponding emission factor can be calculated from Equation (19). The link emission then is obtained from Equation (18) allowing us to derive a PWL link emission function from the PWL link MFD.

Representing the link emissions as a PWL function of the link density is again achieved by using SOS2 constraints and a convex combination of the breakpoints ($k_{i,b_e}^t, E_{i,b_e}^t$) for $b_e \in \{1, \dots, B_e\}$ where $B_e$ is the number of breakpoints on the emission function and thus a model parameter:

$$k_i^t = \sum_{b_e=1}^{B_e} k_{i,b_e}^t \times \gamma_{i,b_e}^t, \qquad (20)$$

$$E_i^t = \sum_{b_e=1}^{B_e} E_{i,b_e}^t \times \gamma_{i,b_e}^t, \qquad (21)$$

$$\text{where } \sum_{b_e=1}^{B_e} \gamma_{i,b_e}^t = 1, \qquad (22)$$

$$\gamma_{i,b_e}^t \ge 0 \forall b_e \in \{1, \dots, B_e\}, \qquad (23)$$

$$\gamma_{i,b_e}^t b_e \in \{1, \dots, B_e\} \text{ is SOS2.} \qquad (24)$$

The MILP formulation of TSE-SO-DTA then reads:

$$\min_{x_i^t} TSE = \sum_{i \in C} \sum_{t \in T} E_i^t. \qquad (25)$$

Subject to: constraints (1)–(16) and constraints (20)–(24).

In comparison to the TSTT with a linear objective function, the PWL objective of the TSE problem induces additional complexity due to the increased number of variables and constraints. Also, such objective functions make the NVH constraints, which are responsible for preventing trivial and suboptimal solutions, even more necessary as discussed later on. Therefore, specific arrangements are needed to preserve a computational burden compatible with practical applications.

# 3 Results and Discussion

## 3.1 Simulation Setting

The suggested framework is implemented on a small network similar to the network, as illustrated in Figure 2, with 6 OD pairs. 2 scenarios are considered. In scenario 1, the demand for each OD pair (d = 0.2 veh/s) is lower than the maximum capacity allowing vehicles to travel at free-flow speed. In scenario 2, the demand is increased (d = 0.4 veh/s)
to make the network congested yet without gridlocks. The simulation is carried out for 2 minutes.

<figure><img src="image_3.png" /><figcaption>**Figure 2:** Simulated network.</figcaption></figure>

For the demand function, the first and last breakpoints of link i are (0, 0) and $(k_{jam}^i, Q_i)$ respectively. For the supply function, they are $(0, Q_i)$ and $(k_{jam}^i, 0)$. Characteristics and other breakpoints for each link are summarized in Table 2. Jam density is set to 0.17 vehicles/m for all links.

## 3.2 Results

First, we investigate the trade-off between TSTT and TSE when each of them is considered as the objective function. The results are summarized in Table 3.

As expected, in case of a higher level of demand the total system travel time and emission values are increased.

The TSE optimization yields the minimum CO₂ emission, but with a higher travel time in comparison to the optimal travel time achieved in the TSTT optimization. The TSE model does not allow the speed values to reach the highest possible most of the time to save CO₂ emissions. As a result, the system-wide travel time is higher for the whole network. Lower TSTT comes at the cost of a higher level of TSE and vice versa.

Second, we compare the results for both TSTT and TSE problems with and without NVH constraints to further scrutinize how they affect the optimization and the solutions. Results are presented in Table 4.

As already mentioned, the NVH constraints play a more important role when solving for TSE. They prevent trivial and underestimated solutions with vehicles staying put to reduce emissions. Their importance, however, becomes less significant in the TSTT problem. This is mainly because vehicles moving along their paths and getting to their destinations as soon as possible contribute to reducing TSTT. This implies the incentive of vehicles to move forward rather than holding back even in the absence of NVH constraints when solving for TSTT.
<table><caption>**Table 2:** Characteristics of the links in the simulated network.</caption><thead><tr><th rowspan="2">Link</th><th rowspan="2">Length<br>(m)</th><th rowspan="2">Max<br>flow<br>(veh/s)</th><th rowspan="2">Speed<br>limit<br>(m/s)</th><th colspan="6">Breakpoints on the MFD</th></tr><tr><th colspan="3">Demand function</th><th colspan="3">Supply function</th></tr></thead><tbody><tr><td>1</td><td>250</td><td>0.5</td><td>12.5</td><td>(0.02,0.25)</td><td>(0.04,0.4)</td><td>(0.06,0.5)</td><td>(0.08,0.5)</td><td>(0.12,0.35)</td><td>(0.14,0.24)</td></tr><tr><td>2</td><td>400</td><td>0.3</td><td>14</td><td>(0.01,0.14)</td><td>(0.02,0.25)</td><td>(0.0265,0.3)</td><td>(0.11,0.3)</td><td>(0.13,0.23)</td><td>(0.15,0.13)</td></tr><tr><td>3</td><td>250</td><td>0.5</td><td>12.5</td><td>(0.02,0.25)</td><td>(0.04,0.4)</td><td>(0.06,0.5)</td><td>(0.08,0.5)</td><td>(0.12,0.35)</td><td>(0.14,0.24)</td></tr><tr><td>4</td><td>250</td><td>0.5</td><td>12.5</td><td>(0.02,0.25)</td><td>(0.04,0.4)</td><td>(0.06,0.5)</td><td>(0.08,0.5)</td><td>(0.12,0.35)</td><td>(0.14,0.24)</td></tr><tr><td>6</td><td>250</td><td>0.5</td><td>12.5</td><td>(0.02,0.25)</td><td>(0.04,0.4)</td><td>(0.06,0.5)</td><td>(0.08,0.5)</td><td>(0.12,0.35)</td><td>(0.14,0.24)</td></tr><tr><td>7</td><td>250</td><td>0.5</td><td>12.5</td><td>(0.02,0.25)</td><td>(0.04,0.4)</td><td>(0.06,0.5)</td><td>(0.08,0.5)</td><td>(0.12,0.35)</td><td>(0.14,0.24)</td></tr><tr><td>8</td><td>250</td><td>0.3</td><td>12.5</td><td>(0.01,0.125)</td><td>(0.02,0.2)</td><td>(0.04,0.3)</td><td>(0.06,0.3)</td><td>(0.1,0.23)</td><td>(0.14,0.12)</td></tr><tr><td>9</td><td>250</td><td>0.5</td><td>12.5</td><td>(0.02,0.25)</td><td>(0.04,0.4)</td><td>(0.06,0.5)</td><td>(0.08,0.5)</td><td>(0.12,0.35)</td><td>(0.14,0.24)</td></tr><tr><td>10</td><td>250</td><td>0.5</td><td>12.5</td><td>(0.02,0.25)</td><td>(0.04,0.4)</td><td>(0.06,0.5)</td><td>(0.08,0.5)</td><td>(0.12,0.35)</td><td>(0.14,0.24)</td></tr><tr><td>12</td><td>300</td><td>0.5</td><td>15</td><td>(0.01,0.15)</td><td>(0.03,0.38)</td><td>(0.05,0.5)</td><td>(0.07,0.5)</td><td>(0.1,0.4)</td><td>(0.14,0.2)</td></tr><tr><td>13</td><td>250</td><td>0.5</td><td>12.5</td><td>(0.02,0.25)</td><td>(0.04,0.4)</td><td>(0.06,0.5)</td><td>(0.08,0.5)</td><td>(0.12,0.35)</td><td>(0.14,0.24)</td></tr><tr><td>14</td><td>250</td><td>0.5</td><td>12.5</td><td>(0.02,0.25)</td><td>(0.04,0.4)</td><td>(0.06,0.5)</td><td>(0.08,0.5)</td><td>(0.12,0.35)</td><td>(0.14,0.24)</td></tr><tr><td>15</td><td>300</td><td>0.5</td><td>15</td><td>(0.01,0.15)</td><td>(0.03,0.38)</td><td>(0.05,0.5)</td><td>(0.07,0.5)</td><td>(0.1,0.4)</td><td>(0.14,0.2)</td></tr><tr><td>16</td><td>250</td><td>0.5</td><td>12.5</td><td>(0.02,0.25)</td><td>(0.04,0.4)</td><td>(0.06,0.5)</td><td>(0.08,0.5)</td><td>(0.12,0.35)</td><td>(0.14,0.24)</td></tr><tr><td>17</td><td>300</td><td>0.5</td><td>15</td><td>(0.01,0.15)</td><td>(0.03,0.38)</td><td>(0.05,0.5)</td><td>(0.07,0.5)</td><td>(0.1,0.4)</td><td>(0.14,0.2)</td></tr><tr><td>19</td><td>250</td><td>0.5</td><td>12.5</td><td>(0.02,0.25)</td><td>(0.04,0.4)</td><td>(0.06,0.5)</td><td>(0.08,0.5)</td><td>(0.12,0.35)</td><td>(0.14,0.24)</td></tr><tr><td>20</td><td>250</td><td>0.5</td><td>12.5</td><td>(0.02,0.25)</td><td>(0.04,0.4)</td><td>(0.06,0.5)</td><td>(0.08,0.5)</td><td>(0.12,0.35)</td><td>(0.14,0.24)</td></tr><tr><td>21</td><td>250</td><td>0.3</td><td>12.5</td><td>(0.01,0.125)</td><td>(0.02,0.2)</td><td>(0.04,0.3)</td><td>(0.06,0.3)</td><td>(0.1,0.23)</td><td>(0.14,0.12)</td></tr><tr><td>22</td><td>250</td><td>0.5</td><td>12.5</td><td>(0.02,0.25)</td><td>(0.04,0.4)</td><td>(0.06,0.5)</td><td>(0.08,0.5)</td><td>(0.12,0.35)</td><td>(0.14,0.24)</td></tr><tr><td>24</td><td>300</td><td>0.5</td><td>15</td><td>(0.01,0.15)</td><td>(0.03,0.38)</td><td>(0.05,0.5)</td><td>(0.07,0.5)</td><td>(0.1,0.4)</td><td>(0.14,0.2)</td></tr><tr><td>25</td><td>250</td><td>0.5</td><td>12.5</td><td>(0.02,0.25)</td><td>(0.04,0.4)</td><td>(0.06,0.5)</td><td>(0.08,0.5)</td><td>(0.12,0.35)</td><td>(0.14,0.24)</td></tr><tr><td>26</td><td>300</td><td>0.5</td><td>15</td><td>(0.01,0.15)</td><td>(0.03,0.38)</td><td>(0.05,0.5)</td><td>(0.07,0.5)</td><td>(0.1,0.4)</td><td>(0.14,0.2)</td></tr></tbody></table>

<table><caption>**Table 3:** TSTT and TSE trade-off.</caption><caption>Scenario 1: 2 minutes of simulation, demand = 0.2 veh/s</caption><thead><tr><th>Objective</th><th>TSTT (s)</th><th>TSE (g)</th></tr></thead><tbody><tr><td>Minimizing TSTT</td><td>7018</td><td>7730</td></tr><tr><td>Minimizing TSE</td><td>7200</td><td>7218</td></tr></tbody></table>

<table><caption>**Table 4:** Comparison of results with and without NVH.</caption><caption>Scenario 2: 2 minutes of simulation, demand = 0.4 veh/s</caption><thead><tr><th>Objective</th><th>TSTT (s)</th><th>TSE (g)</th></tr></thead><tbody><tr><td>Minimizing TSTT</td><td>14143</td><td>14629</td></tr><tr><td>Minimizing TSE</td><td>14399</td><td>14074</td></tr></tbody></table>

<table><caption>2 minutes of simulation, demand = 0.4 veh/s</caption><thead><tr><th rowspan="2"></th><th colspan="2">TSTT</th><th colspan="2">TSE</th></tr><tr><th>Objective value (s)</th><th>Calculation time (s)</th><th>Objective value (g)</th><th>Calculation time (s)</th></tr></thead><tbody><tr><td>With NVH</td><td>14143</td><td>6</td><td>14074</td><td>905</td></tr><tr><td>Without NVH</td><td>14169</td><td>3</td><td>11585</td><td>17</td></tr></tbody></table>
<table><caption>**Table 5:** Sensitivity analysis to number of breakpoints and path selection.

**2 minutes of simulation, demand = 0.4 veh/s, with NVH constraints**</caption><thead><tr><th rowspan="2">BP</th><th colspan="2">All possible paths</th><th colspan="2">Path selection</th></tr><tr><th>TSE (g)</th><th>Calculation time (s)</th><th>TSE (g)</th><th>Calculation time (s)</th></tr></thead><tbody><tr><td>8</td><td>14074</td><td>905</td><td>14195</td><td>10</td></tr><tr><td>6</td><td>13755</td><td>108</td><td>14119</td><td>7</td></tr><tr><td>4</td><td>13209</td><td>22</td><td>13761</td><td>4</td></tr></tbody></table>

Despite the importance of the NVH constraints, they increase the calculation time noticeably, especially for the TSE problem. To alleviate the calculation burden, we study several alternatives. We analyze the sensitivity of the results and solution algorithm to the number of breakpoints on the PWL emission function. A path selection strategy is also implemented in which only two alternative paths for each OD pair are accessible to the users of the network. In Table 5 some initial results are presented.

Increasing the number of breakpoints (BP) on the PWL emission function increases the accuracy of the solution and prevents suboptimality. However, this comes at the cost of higher calculation time stemming from the increased complexity of the solution algorithm to take into account more breakpoints and corresponding variables and constraints.

The computational burden can be further decreased by employing path selection strategies. Results suggest a significant decrease in calculation time when the set of feasible paths for each OD is restricted to the first and second shortest path.

We are currently investigating different alternatives to further tackle the computational challenges. Those results will be presented at the MFTS 2022 conference.

## References

[Azi12] H. M. A. AZIZ and S. V. UKKUSURI: "Integration of Environmental Objectives in a System Optimal Dynamic Traffic Assignment Model". In: *Computer-Aided Civil and Infrastructure Engineering* 27.7 (Aug. 2012), pages 494–511. ISSN: 1093-9687. DOI: 10.1111/j.1467-8667.2012.00756.x.

[Bea69] E. BEALE and J. TOMLIN: "Special facilities in a general mathematical programming system for nonconvex problems using ordered sets of variables". In: *Operational Research* 69 (Jan. 1969), pages 447–454. ISSN: 1866-1505.

[Cit17] Yearly Activity Report. Technical report. Citepa, 2017. URL: https://www.citepa.org/wp-content/uploads/publications/rapports-activite/citepa-ra-2017.pdf.

[EEA22] COPERT: *The Industry Standard Emissions Calculator*. European Environment Agency, 2022. URL: https://www.emisia.com/utilities/copert/.
[Gha95] M. O. GHALI and M. J. SMITH: "A model for the dynamic system optimum traffic assignment problem". In: *Transportation Research Part B: Methodological* 29.3 (June 1995), pages 155-170. ISSN: 0191-2615. DOI: 10.1016/0191-2615(94)00024-T.

[Keh04] A. B. KEHA, I. R. de FARIAS, and G. L. NEMHAUSER: "Models for representing piecewise linear cost functions". In: *Operations Research Letters* 32.1 (Jan. 2004), pages 44-48. ISSN: 0167-6377. DOI: 10.1016/S0167-6377(03)00059-2.

[Lon18] J. LONG, J. CHEN, W. Y. SZETO, and Q. SHI: "Link-based system optimum dynamic traffic assignment problems with environmental objectives". In: *Transportation Research Part D: Transport and Environment* 60 (May 2018), pages 56-75. ISSN: 1361-9209. DOI: 10.1016/j.trd.2016.06.003.

[Lon19] J. LONG and W. Y. SZETO: "Link-Based System Optimum Dynamic Traffic Assignment Problems in General Networks". In: *Operations Research* 67.1 (Jan. 2019), pages 167-182. ISSN: 0030-364X. DOI: 10.1287/opre.2018.1775.

[Sha22] N. SHAKOORI, G. de NUNZIO, L. LECLERCQ, and A. SCIARRETTA: "A MILP Framework to Solve System Optimum with Link MFD Functions". In: *hEART 2022: 10th Symposium of the European Association for Research in Transportation*. June 2022. URL: https://transp-or.epfl.ch/heart/2022/abstracts/189.pdf.

[She84] Y. SHEFFI: *Urban Transportation Networks: Equilibrium Analysis With Mathematical Programming Methods*. Englewood Cliffs, USA: Prentice-Hall, 1984. ISBN: 0-139-39729-9.

[Zil00] A. ZILIASKOPOULOS: "A Linear Programming Model for the Single Destination System Optimum Dynamic Traffic Assignment Problem". In: *Transportation Science* 34 (Feb. 2000), pages 37-49. ISSN: 0041-1655. DOI: 10.1287/trsc.34.1.37.12281.

Corresponding author: Niloofar Shakoori, IFP Energies nouvelles, Rueil-Malmaison, France,
e-mail: niloofar.shakoori@ifpen.fr