Skip to main content.

This page’s menu:

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 Ci=(xi,yi,di,ei,li) where (xi,yi)) is the location of the customer, di is the demand, and [ei,li] 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 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.

Model of airplane landing cost

Input

We are given a number aircrafts with Ai=(Ei,Ti,Li,ei,li,di,ki) where ki 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:

Ci(t)=max(0,Ti-t) ⋅ ei + max(0,t-Ti) ⋅ di ⋅ li

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 Ai a landing time Ei ≤ ti ≤ Li and a runway 1 ≤ ri ≤ R such that

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 t3 cannot start executing until the results of both tasks t1 and t2 are available. The available resources are two processors, p1 and p2, 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, t1 can only execute on p1, t2 only on p2, and t3 can execute on both p1 and p2.

The energy-optimal schedule is achieved by letting t1 and t2 execute on p1 and p2, respectively, broadcast the result of t2 on the bus, and execute t3 on p1, which consumes the total of 127 energy units. On the other hand, broadcasting the result of t1 on the bus and executing t3 on p2 requires 141 energy units. Both schedules are depicted as Gantt charts in the figure.

An Energy Task Graph

Input

The ETGS problem is given as a 8-tuple (T,P,<,δ,π,τ,κ,D) where T={t1,...,tn} is a the set of tasks, P={p1,...,pk} is the set of processors (or machines), < is an irreflexive preorder on T giving the precedence constraints, δ = {δ11n112,...,δnk} where each δij∈ N ∪ {∞}, N is the set of natural numbers, gives the execution time of task ti on processor pj, π = {πbus1,...,πk} gives the energy consumption of the bus and processor while operating, τ = {τbus1,...,τ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, ti, a triple (ai,bi,ci) stating that at time ai, task ti should start executing on processor bi and the result should be broadcasted on the bus at time ci. 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.