Air transport
Description
| Problem name and type, features | Difficulty | Related examples |
| F‑1 | Flight connections at a hub: Assignment problem | * | assignment_graph.mos, i1assign.mos, c6assign.mos |
|---|
| |
| F‑2 | Composing flight crews: Bipartite matching | **** | matching_graph.mos |
|---|
| 2 problems, data preprocessing, incremental definition of data array, encoding of arcs, logical or (cumulative version) and and, procedure for printing solution, forall-do, max, finalize |
| F‑3 | Scheduling flight landings: Scheduling problem with time windows | *** | |
|---|
| generalization of model to arbitrary time windows; calculation of specific BigM, forall-do |
| F‑4 | Airline hub location: Hub location problem | *** | |
|---|
| quadruple indices; improved (re)formulation (first model not usable with student version), union of index (range) sets |
| F‑5 | Planning a flight tour: Symmetric traveling salesman problem | ***** | tsp_graph.mos |
|---|
| loop over problem solving, TSP subtour elimination algorithm; procedure for generating additional constraints, recursive subroutine calls, working with sets, forall-do, repeat-until, getsize, not |
Further explanation of this example:
'Applications of optimization with Xpress-MP', Chapter 11: Air transport
Source Files
By clicking on a file name, a preview is opened at the bottom of this page.
Data Files
f4hub.mos
(!******************************************************
Mosel Example Problems
======================
file f4hub.mos
``````````````
Choosing hubs for transatlantic freight
An airline specializes in freight transportation linking
major cities in France with American cities. The average
freight quantities transported between each city is known.
Assume the transportation cost is proportional to the
distance between the cities. The airline is planning to
use two cities as hubs to reduce costs. The traffic between
cities assigned to one hub and the cities assigned to the
other hub is all routed through the single connection from
H1 to H2. The transport cost between the two hubs decreases
by 20%. Determine the two cities to be assigned as hubs in
order to minimize the total transportation costs.
This problem uses quadruple indices to represent the cost
of traveling from city i to j via hubs k and l. The formulation
of the mathematical model uses a large number of variables
for a relatively small problem.
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, Mar. 2002
*******************************************************!)
model "F-4 Hubs"
uses "mmxprs"
declarations
CITIES = 1..6 ! Cities
NHUBS = 2 ! Number of hubs
COST: array(CITIES,CITIES,CITIES,CITIES) of real ! (i,j,k,l) Transport cost
! from i to j via hubs k and l
QUANT: array(CITIES,CITIES) of integer ! Quantity to transport
DIST: array(CITIES,CITIES) of integer ! Distance between cities
FACTOR: real ! Reduction of costs between hubs
flow: array(CITIES,CITIES,CITIES,CITIES) of mpvar ! flow(i,j,k,l)=1 if
! freight from i to j goes via k & l
hub: array(CITIES) of mpvar ! 1 if city is a hub, 0 otherwise
end-declarations
initializations from 'f4hub.dat'
QUANT DIST FACTOR
end-initializations
! Calculate costs
forall(i,j,k,l in CITIES)
COST(i,j,k,l):= DIST(i,k)+FACTOR*DIST(k,l)+DIST(l,j)
! Objective: total transport cost
Cost:= sum(i,j,k,l in CITIES) QUANT(i,j)*COST(i,j,k,l)*flow(i,j,k,l)
! Number of hubs
sum(i in CITIES) hub(i) = NHUBS
! One hub-to-hub connection per freight transport
forall(i,j in CITIES) sum(k,l in CITIES) flow(i,j,k,l) = 1
! Relation between flows and hubs
forall(i,j,k,l in CITIES) do
flow(i,j,k,l) <= hub(k)
flow(i,j,k,l) <= hub(l)
end-do
forall(i in CITIES) hub(i) is_binary
forall(i,j,k,l in CITIES) flow(i,j,k,l) is_binary
! Solve the problem
minimize(Cost)
! Solution printing
declarations
NAMES: array(CITIES) of string ! Names of cities
end-declarations
initializations from 'f4hub.dat'
NAMES
end-initializations
writeln("Total transport cost: ", strfmt(getobjval,10,2))
write("Hubs:")
forall(i in CITIES | getsol(hub(i))>0) write(" ",NAMES(i))
writeln
end-model
|
