# CORA Case Studies and Examples

- Vehicle Routing Problem with Time Windows
- Aircraft Landing Problem
- Energy Optimal Task Graph Scheduling

## 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*is the location of the customer,

_{i},y_{i}))*d*is the demand, and

_{i}*[e*is the time window. Furthermore, we a given a number,

_{i},l_{i}]*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*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:

_{i}_{i}(t)=max(0,T

_{i}-t) ⋅ e

_{i}+ max(0,t-T

_{i}) ⋅ d

_{i}⋅ l

_{i}_

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*and a runway

_{i}≤ t_{i}≤ L_{i}*1 ≤ r*such that

_{i}≤ R*∑*is minimal_{i}C_{i}(t_{i})*sep(k*whenever_{i},k_{j}) ≤ k_{i}-k_{j}*i ≠ j*,*t*, and_{i}≥ t_{j}*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*and

_{1}*t*are available. The available resources are two processors,

_{2}*p*and

_{1}*p*, and a single bus with energy consumptions

_{2}*π*,

_{1}=4*π*, and

_{2}=3*π*per time unit when operating and

_{bus}=10*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*can only execute on

_{1}*p*,

_{1}*t*only on

_{2}*p*, and

_{2}*t*can execute on both

_{3}*p*and

_{1}*p*.

_{2}The energy-optimal schedule is achieved by letting *t _{1}* and

*t*execute on

_{2}*p*and

_{1}*p*, respectively, broadcast the result of

_{2}*t*on the bus, and execute

_{2}*t*on

_{3}*p*, which consumes the total of 127 energy units. On the other hand, broadcasting the result of

_{1}*t*on the bus and executing

_{1}*t*on

_{3}*p*requires 141 energy units. Both schedules are depicted as Gantt charts in the figure.

_{2}### 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*is the set of processors (or machines),

_{1},…,p_{k}}*<*is an irreflexive preorder on

*T*giving the precedence constraints,

*δ = {δ*where each

_{11},δ_{n1},δ_{12},…,δ_{nk}}*δ*,

_{ij}∈ N ∪ {∞}*N*is the set of natural numbers, gives the execution time of task

*t*on processor

_{i}*p*,

_{j}*π = {π*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,

_{bus},τ_{1},…,τ_{k}}*κ = {κ*gives the communication time for sending tasks over the bus, and

_{1},…,κ_{n}}*D*is the deadline.

### Problem

Assign to each task, *t _{i}*, a triple

*(a*stating that at time

_{i},b_{i},c_{i})*a*, task

_{i}*t*should start executing on processor

_{i}*b*and the result should be broadcasted on the bus at time

_{i}*c*. 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.

_{i}