Case Studies
Vehicle Routing Problem with Time Windows
The vehicle routing problem with time windows (VRPTW) is a generalization of the travelling salesman problem with multiple salesmen. Consider a business located at (0,0) in a two-dimensional coordinate system. The business produces some goods and ships it to a number of dispersed customers in the coordinate system. Each customer has a specific demand and must be served within a given time window. Available to the business is a fleet of vehicles with limited capacity, now, the problem is to assign routes to each vehicle such that each customer demand is met within the designated time windows and the vehicle returns to the business. Several objective functions can be used for optimization in this scenario, e.g. the total length of the routes, the total time taken to execute the routes, etc.
Input
We are given a number of customers C_{i}=(x_{i},y_{i},d_{i},e_{i},l_{i}) where (x_{i},y_{i})) is the location of the customer, d_{i} is the demand, and [e_{i},l_{i}] is the time window. Furthermore, we a given a number, m, of vehicles with capacity c.
Problem
Assign to each vehicle a route such that:
- The objective function is minimized.
- The total demand of a route does not exceed c.
- Each customer on the route will be visited in the interval [e_{i},l_{i}].
The particular objective function used in the example is the sum of a ⋅ sum(distance) + b ⋅ end_time + c ⋅ (max(0, sum(demand)-K)) for every route, where a,b,c are constants and K is some percentage of the capacity.
Download
The UPPAAL model and specification can be downloaded.
Aircraft Landing Problem
The aircraft landing problem (ALP) was first provided in [BKS00] solved using mixed integer linear programming (MILP). The problem consists of a number of aircrafts that need to land on limited number of runways. Each aircraft has a preferred target landing time, corresponding to arriving at the runway with cruise speed and landing immediately. However, the aircraft can speed up and land earlier or stay longer in the air and land later if necessary. Due to extra gas used in accelerating, landing earlier has an added cost which grows linearly until some fixed earliest landing time. Late landings have an immediate constant penalty for landing late and a cost growing linearly with the amount of gas used for staying in the air until all latest possible (controlled) landing time. The cost function for a single aircraft is given in the figure below.
Furthermore, aircrafts cannot land back to back on the same runway due to wake turbulence. Thus, there are certain minimum constraints on the separation delay between aircrafts of different types, e.g. a Boeing 747 can handle (and generates) more turbulence than a Hawker 700.
Now, the problem is to assign landing times and runways to all aircrafts while respecting individual timing constraints for the aircrafts and the wake turbulence constraints.
Input
We are given a number aircrafts with A_{i}=(E_{i},T_{i},L_{i},e_{i},l_{i},d_{i},k_{i}) where k_{i} is the kind of aircraft and the rest of the parameters are as given in the figure above. The parameters for each aircraft define a function:
as depicted in the figure above. Furthermore, separation function sep(a,b), which gives the required separation between two aircrafts of types a and b landing on the same runway. Finally, we are given a number, R, of runways.
Problem
Assign to each aircraft A_{i} a landing time E_{i} ≤ t_{i} ≤ L_{i} and a runway 1 ≤ r_{i} ≤ R such that
- ∑_{i} C_{i}(t_{i}) is minimal
- sep(k_{i},k_{j}) ≤ k_{i}-k_{j} whenever i ≠ j, t_{i} ≥ t_{j}, and r_{i} = r_{j}.
Download
The UPPAAL model and specification can be downloaded.
Energy Optimal Task Graph Scheduling
Energy-optimal task graph scheduling (ETGS) is the problem of scheduling a number of interdependent tasks onto a number heterogeneous processors that communicate through a single bus while minimizing the overall energy requirement and meeting an overall deadline. The interdependencies state that a task cannot execute until the results of all predecessors in the graph have been computed. Moreover, the results should be available in the sense that either each of the predecessors have been computed on the same processor, or on a different processor and the result has been broadcasted on the bus. An example task graph with three tasks is depicted in the figure below. The task t_{3} cannot start executing until the results of both tasks t_{1} and t_{2} are available. The available resources are two processors, p_{1} and p_{2}, and a single bus with energy consumptions π_{1}=4, π_{2}=3, and π_{bus}=10 per time unit when operating and 1 when idle. For real applications energy consumption is, usually, measured in mW and execution times in ms. The nodes in the figure are annotated with their execution times on the processors, that is, t_{1} can only execute on p_{1}, t_{2} only on p_{2}, and t_{3} can execute on both p_{1} and p_{2}.
The energy-optimal schedule is achieved by letting t_{1} and t_{2} execute on p_{1} and p_{2}, respectively, broadcast the result of t_{2} on the bus, and execute t_{3} on p_{1}, which consumes the total of 127 energy units. On the other hand, broadcasting the result of t_{1} on the bus and executing t_{3} on p_{2} requires 141 energy units. Both schedules are depicted as Gantt charts in the figure.
Input
The ETGS problem is given as a 8-tuple (T,P,<,δ,π,τ,κ,D) where T={t_{1},...,t_{n}} is a the set of tasks, P={p_{1},...,p_{k}} is the set of processors (or machines), < is an irreflexive preorder on T giving the precedence constraints, δ = {δ_{11},δ_{n1},δ_{12},...,δ_{nk}} where each δ_{ij}∈ N ∪ {∞}, N is the set of natural numbers, gives the execution time of task t_{i} on processor p_{j}, π = {π_{bus},π_{1},...,π_{k}} gives the energy consumption of the bus and processor while operating, τ = {τ_{bus},τ_{1},...,τ_{k}} gives the energy consumption of the bus and processor while idle, κ = {κ_{1},...,κ_{n}} gives the communication time for sending tasks over the bus, and D is the deadline.
Problem
Assign to each task, t_{i}, a triple (a_{i},b_{i},c_{i}) stating that at time a_{i}, task t_{i} should start executing on processor b_{i} and the result should be broadcasted on the bus at time c_{i}. This assignment should minimizes the total energy consumption while respecting the precedence constraints and never letting the bus or processors be utilized by more than one task at any time.