Sustainable Transport and Logistics
Tutorials
EBM249A05
Mathematical Modeling................................................................................................................................. 2
Linear programming model formulation......................................................................................................... 4
Solving linear programming models graphically..............................................................................................5
Center of gravity method............................................................................................................................... 6
Factor Rating Method.................................................................................................................................... 9
Cost-volume Analysis................................................................................................................................... 10
Facility Location Problem (FLP)..................................................................................................................... 11
Network Design Problem............................................................................................................................. 12
Vehicle Routing Problems............................................................................................................................. 16
Solving vehicle routing problems with the nearest neighbor heuristic...........................................................22
Solving vehicle routing problems with the Clarke and Wright savings heuristic..............................................24
Route Length Approximation........................................................................................................................ 25
,Mathematical Modeling
Terminology
- Decision variables
o Mathematical description of the set of decisions to be made
- Parameters
o What input data are known and needed for making the decisions?
- Objective
o A measure to rank alternative solutions
o What do you want to achieve? Express this mathematically by using your decision
variables and parameters
- Constraints
o Limitations on the values of the decision variables
o Develop mathematical relationships to describe constraints
Types of mathematical models
- Linear programming
o Variables can take real numbers
- Integer programming
o Variables can only take integer values
- Binary programming
o Variables can only take the value 0 or 1
- Mixed integer programming
o Some variables are constrained to be integer values
Valid range of a variable
- Binary programming: 𝑥 ∈ 0,1
- Integer programming: 𝑥 ∈ ℕ, ℤ
o Either non-negative: ℕ is the set containing all positive integers: {1,
2, …)
o Or all integer numbers: ℤ is the set containing zero, all positive
integers, and all negative integers
- Linear programming: 𝑥 ∈ ℝ
o ℝ is the set containing all rational numbers and irrational numbers
(such as 2 and 𝜋)
Feasible vs infeasible solution
- A feasible solution satisfies all of the constraints
o That is, any point within the feasible region
o Note that sometimes a feasible solution may not exist at all
- Feasible region is a convex area
o All points on the constraint lines that form the boundary of the feasible region are
feasible solutions
Finding optimal solutions
- Optimal versus non-optimal
o Exact algorithms give an optimal solution
o Heuristics are simple procedures guided by common sense that are meant to provide
feasible but not necessarily optimal solutions to difficult problems
2
, - An optimal solution can be found in a corner point, or on a constraint line between two
corner points
- Any point in the interior of the feasible region cannot be an optimal solution
Set notations
- 𝐴 = 𝑎, 𝑏, 𝑐 for a set “A” contains the elements “a”, “b”, and “c”
o 𝑎 ∈ 𝐴 (denoting that a is an element of A)
o 𝐴 ∋ 𝑎 (denoting that A has a as an element)
o 4 ∉ 𝐴 (denoting that 4 is not an element of A)
o 𝑎, 𝑏 ⊆ 𝐴 (denoting that the set 𝑎, 𝑏 is a subset of A)
- Using set builder notation
o 𝑆 = 1, 2, 3, … , 𝑛
o S=𝑥1≤𝑥≤𝑛
o Where the “|” means such that, or s.t.
Summation
Other useful notation
- Quantifiers
o ∀ (universal quantifier) means “for all.”
o ∃ (existential quantifier) means “there exists.”
- Example: ∀ 𝑧 ∈ ℤ ∃ 𝑧’ ∈ ℤ s.t. 𝑧’ > 𝑧
o For every 𝑧 that is an integer number, there exists another integer number 𝑧’ that is
larger than 𝑧
3
Tutorials
EBM249A05
Mathematical Modeling................................................................................................................................. 2
Linear programming model formulation......................................................................................................... 4
Solving linear programming models graphically..............................................................................................5
Center of gravity method............................................................................................................................... 6
Factor Rating Method.................................................................................................................................... 9
Cost-volume Analysis................................................................................................................................... 10
Facility Location Problem (FLP)..................................................................................................................... 11
Network Design Problem............................................................................................................................. 12
Vehicle Routing Problems............................................................................................................................. 16
Solving vehicle routing problems with the nearest neighbor heuristic...........................................................22
Solving vehicle routing problems with the Clarke and Wright savings heuristic..............................................24
Route Length Approximation........................................................................................................................ 25
,Mathematical Modeling
Terminology
- Decision variables
o Mathematical description of the set of decisions to be made
- Parameters
o What input data are known and needed for making the decisions?
- Objective
o A measure to rank alternative solutions
o What do you want to achieve? Express this mathematically by using your decision
variables and parameters
- Constraints
o Limitations on the values of the decision variables
o Develop mathematical relationships to describe constraints
Types of mathematical models
- Linear programming
o Variables can take real numbers
- Integer programming
o Variables can only take integer values
- Binary programming
o Variables can only take the value 0 or 1
- Mixed integer programming
o Some variables are constrained to be integer values
Valid range of a variable
- Binary programming: 𝑥 ∈ 0,1
- Integer programming: 𝑥 ∈ ℕ, ℤ
o Either non-negative: ℕ is the set containing all positive integers: {1,
2, …)
o Or all integer numbers: ℤ is the set containing zero, all positive
integers, and all negative integers
- Linear programming: 𝑥 ∈ ℝ
o ℝ is the set containing all rational numbers and irrational numbers
(such as 2 and 𝜋)
Feasible vs infeasible solution
- A feasible solution satisfies all of the constraints
o That is, any point within the feasible region
o Note that sometimes a feasible solution may not exist at all
- Feasible region is a convex area
o All points on the constraint lines that form the boundary of the feasible region are
feasible solutions
Finding optimal solutions
- Optimal versus non-optimal
o Exact algorithms give an optimal solution
o Heuristics are simple procedures guided by common sense that are meant to provide
feasible but not necessarily optimal solutions to difficult problems
2
, - An optimal solution can be found in a corner point, or on a constraint line between two
corner points
- Any point in the interior of the feasible region cannot be an optimal solution
Set notations
- 𝐴 = 𝑎, 𝑏, 𝑐 for a set “A” contains the elements “a”, “b”, and “c”
o 𝑎 ∈ 𝐴 (denoting that a is an element of A)
o 𝐴 ∋ 𝑎 (denoting that A has a as an element)
o 4 ∉ 𝐴 (denoting that 4 is not an element of A)
o 𝑎, 𝑏 ⊆ 𝐴 (denoting that the set 𝑎, 𝑏 is a subset of A)
- Using set builder notation
o 𝑆 = 1, 2, 3, … , 𝑛
o S=𝑥1≤𝑥≤𝑛
o Where the “|” means such that, or s.t.
Summation
Other useful notation
- Quantifiers
o ∀ (universal quantifier) means “for all.”
o ∃ (existential quantifier) means “there exists.”
- Example: ∀ 𝑧 ∈ ℤ ∃ 𝑧’ ∈ ℤ s.t. 𝑧’ > 𝑧
o For every 𝑧 that is an integer number, there exists another integer number 𝑧’ that is
larger than 𝑧
3
