#
# ZIMPL model file for the minimum tollbooth (MINTB) problem.
#
# Author: Paul A. Rubin (rubin@msu.edu)
#
# Description: the MINTB problem searches for a minimal collection of
# arcs from a multicommodity traffic network (a digraph where each "commodity"
# is an origin/destination pair) and a set of nonnegative tolls on those arcs
# such that asserting those tolls (and only those tolls) causes the user
# equilibrium flow (the flow obtained when each traveler adopts the path
# that minimizes their personal cost, where cost balances travel time,
# a function of distance and congestion, with tolls paid) to match the
# system equilibrium solution (the flow pattern a central planner would
# select so as to minimize total travel times).
#
# References:
#
# @INPROCEEDINGS{Bai2006,
# author = {Lihui Bai and Matthew T. Stamps and R. Corban Harwood and Christopher J. Kollmann},
# title = {A Genetic Algorithm for the Minimum Tollbooth Problem},
# booktitle = {Proceedings of the 2006 Meeting of the Decision Sciences Institute},
# year = {2006}
# }
#
# @ARTICLE{Bai2009,
# author = {Lihui Bai and Paul A. Rubin},
# title = {Combinatorial Benders Cuts for the Minimum Tollbooth Problem},
# journal = {Operations Research},
# year = {2009},
# volume = {57},
# pages = {1510--1522},
# number = {6},
# month = {November-December}
# }
#
# specify data file here or in the ZIMPL command line
param datafile := "stockholm.zdat";
# parameters and index sets
param nNodes := read datafile as "1n" use 1 comment "#"; # number of nodes in the network
param nArcs := read datafile as "2n" use 1 comment "#"; # number of arcs
param nOD := read datafile as "3n" use 1 comment "#"; # number of OD pairs
param maxToll := read datafile as "4n" use 1 comment "#"; # upper bound on individual tolls (M in the papers)
param minFlow := 0.001; # minimum flow to count as nonzero -- used to compute set USED[] below
set NODE := {read datafile as "<2n>" skip 1 use nArcs comment "#"} + {read datafile as "<3n>" skip 1 use nArcs comment "#"}; # node index set (nodes may not be numbered consecutively, and nodes may be origins only, destinations only or both)
do check card(NODE) == nNodes;
set ARC := {read datafile as "<2n, 3n>" skip 1 use nArcs comment "#"}; # arc set (A in the papers)
do check card(ARC) == nArcs;
set OD := {read datafile as "<1n>" skip (1 + nArcs) comment "#"}; # OD index set (K in the papers) (OD pairs may not be numbered consecutively)
do check card(OD) == nOD;
param flow[OD*ARC] := read datafile as "<1n, 2n, 3n> 4n" skip (1 + nArcs) comment "#";
param epsilon[OD*ARC] := read datafile as "<1n, 2n, 3n> 5n" skip (1 + nArcs) comment "#"; # relaxation parameter (epsilon in the papers)
set USED[ in OD] := { * in ARC with flow[od, i, j] > minFlow}; # arcs with positive system equilibrium flows for a given OD pair (\bar{x}^k_{i,j} > 0 in the papers)
param delay[ARC] := read datafile as "<2n, 3n> 5n" skip 1 use nArcs comment "#"; # the travel delay on each arc in the system equilibrium solution (s(\bar{v}) in the papers)
# variables
var tollCharge [ARC] >= 0; # tolls charged (beta in the papers)
var willToll [ARC] binary; # indicator of arcs to be tolled (y in the papers)
var mult [OD*NODE] >= -infinity <= infinity; # KKT multipliers (rho in the papers)
# objective
minimize NumberTolled: sum ** in ARC : willToll[i, j];
# constraint: equilibrium lower bound on toll (all od/arc pairs)
subto TollLB:
forall in OD do
forall ** in ARC do
mult[od, i] - mult[od, j] - tollCharge[i, j] <= delay[i, j];
# constraint: equilbrium upper bound on toll (od/arc pairs with equilibrium flows only)
subto TollUB:
forall in OD do
forall ** in USED[od] do
mult[od, i] - mult[od, j] - tollCharge[i, j] >= delay[i, j] - epsilon[od, i, j];
# constraint: no toll charge on untolled arcs
subto CanCharge:
forall ** in ARC do
tollCharge[i, j] - maxToll*willToll[i, j] <= 0;
# read the data
*