KAIST Discrete Math Seminar

This short course covers selected topics in mathematical models arising in the analysis of transportation systems and networks. We will briefly review basic topics in network optimization and then will proceed to commonly used models for logistics service planning by private companies as well as management of public vehicular infrastructure. This course will cover topics such as risk-averse routing, vehicle routing problems, network user equilibrium, road pricing and network design, location problems, and modeling drivers’ decision making processes, with applications in bike-sharing services, electric-vehicle charging, hazardous materials transportation, and congestion mitigation. This course will also introduce some computational tools available in the Julia Language.Outline (subject to change)

1. Basic Topics in Network Optimization
– Shortest Path Problem
– Minimum Cost Network Flow
– Transportation Problem
– Multi-Commodity Network Flow
– Intro to Julia and JuMP

2. Risk-Averse Routing
– Robust Shortest Path Problem
* Scenario-based
* Interval data
* Polyhedral uncertainty set
* Two multiplicative coefficients
* Julia: RobustShortestPath.jl
– Value-at-Risk
– Conditional Value-at-Risk
– Worst-case Conditional Value-at-Risk

3. Vehicle Routing Problem
– Traveling Salesman Problem
– Subtour Elimination
– Vehicle Routing Problem
– VRP with Time Windows
– Green VRP / Electric-VRP
– Energy Minimizing VRP
– Medical-Waste Collection VRP
– Bike-Balancing VRP

4. Network User Equilibrium
– System Optimum
– User Equilibrium
* Complementarity Problem
* Variational Inequality Problem
– Computation
* Frank-Wolfe Algorithm
* Julia: VariationalInequality.jl
* Julia: Complementarity.jl
* Julia: TrafficAssignment.jl
– Stochastic User Equilibrium
– Braess Paradox
– Price of Anarchy

5. Network Regulation
– Bilevel Optimization
– Road Pricing
– Network Design
– Inverse Optimization for Road Pricing
– Single-level Reformulation
– Leader-Follower Game

6. Location Problems
– Classic Location Problems
* p-median
* p-center
* set-covering
* maximal covering
* fixed-charge facility location
* two-stage problem
– Hub Location Problems
* p-hub center
* hub-covering
* p-hub median
– Lagrangian Relaxation
– Flow-Capturing Location Problem
– Flow-Refueling Location Problem
– Infrastructure Planning for Electric Vehicles

7. Generalized Bounded Rationality
– Satisficing Behavior
– Perception-Error
– Equivalence
– Comparison with Random-Utility Model
– Monte-Carlo Method
– Julia: PathDistribution.jl
– Application in Robust Network Design