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
f3landing.mos
(!******************************************************
Mosel Example Problems
======================
file f3landing.mos
``````````````````
Schedule plane landings
Ten planes are scheduled to arrive at a large airport.
Each plane has an earliest and latest arrival time. Within
this time window, there is a target arrival time. Penalties
are assigned to each minute a flight is early or late. Between
each landing, there is a required security time interval.
Which schedule minimizes the total arrival penalty given the
arrival time windows and required separating intervals?
This problem calculates a specific BigM per index tuple for use
in the formulation of the disjunctive constraints on landing times.
Note that the obvious pair of 'START' and 'END' for the time
windows cannot be used because 'END' is a reserved word in Mosel.
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, Mar. 2002
*******************************************************!)
model "F-3 Landing schedule"
uses "mmxprs"
declarations
PLANES = 1..10 ! Set of airplanes
START, STOP: array(PLANES) of integer ! Start, end of arrival time windows
TARGET: array(PLANES) of integer ! Planned arrival times
CEARLY, CLATE: array(PLANES) of integer ! Cost of earliness/lateness
DIST: array(PLANES,PLANES) of integer ! Minimum interval between planes
M: array(PLANES,PLANES) of integer ! Sufficiently large positive values
prec: array(PLANES,PLANES) of mpvar ! 1 if plane i precedes j
land: array(PLANES) of mpvar ! Arrival time
early,late: array(PLANES) of mpvar ! Earliness/lateness
end-declarations
initializations from 'f3landing.dat'
START STOP TARGET CEARLY CLATE DIST
end-initializations
forall(p,q in PLANES) M(p,q):= STOP(p) + DIST(p,q) - START(q)
! Objective: total penalty for deviations from planned arrival times
Cost:= sum(p in PLANES) (CEARLY(p)*early(p) + CLATE(p)*late(p))
! Keep required intervals between plan arrivals
forall(p,q in PLANES | p>q)
land(p) + DIST(p,q) <= land(q) + M(p,q)*prec(q,p)
forall(p,q in PLANES | p<q)
land(p) + DIST(p,q) <= land(q) + M(p,q)*(1-prec(p,q))
! Relations between earliness, lateness, and effective arrival time
forall(p in PLANES) do
early(p) >= TARGET(p) - land(p)
late(p) >= land(p) - TARGET(p)
land(p) = TARGET(p) - early(p) + late(p)
end-do
forall(p in PLANES) do
START(p) <= land(p); land(p) <= STOP(p)
early(p) <= TARGET(p)-START(p)
late(p) <= STOP(p)-TARGET(p)
end-do
forall(p,q in PLANES | p<q) prec(p,q) is_binary
! Solve the problem
minimize(Cost)
! Solution printing
writeln("Total deviation cost: ", getobjval)
writeln("Plane Arrival Target Deviation")
forall(p in PLANES)
writeln(strfmt(p,3), strfmt(getsol(land(p)),8), strfmt(TARGET(p),8),
strfmt(getsol(land(p))-TARGET(p),8))
end-model
|
