Trains Scheduling Problem

The tracks in the following figure show the routes of $5$ trains, each starting from a starting

station $S_i$ to a terminating station $T_i.$ The orange circles indicate the stations the trains must pass

through and the arrows indicate the track followed by each train. You may assume that the

trains take exactly one hour to move from one station to the next.

Given that the trains must begin their journeys in the morning, at either $8\mathrm{.}00,9\mathrm{.}00$ or $10\mathrm{.}00,$ we

would like to come up with a safe schedule $($assigning a valid starting time$)$ for all trains such that

the following constraints are satisfied:

No two trains arrive at any intersecting station at the same time. For example, Train $2$ and

Train $3$ cannot depart at the same time because they would collide at the next station

All trains must arrive at their final destination on or before $14$:$00.$

When a train starts its journey, it can only terminate at the final destination.

Use this information to answer each of the following questions:

Question $1$: $[$Warm up$]$

a$)$ Given that all trains must depart at either $8$:$00,9$:$00,$ or $10$:$00$ and looking at the track

travelled by Train $1,$ what can you say about its departure time?

b$)$ If Train $1$ starts its journey at $8$:$00,$ list all the times that Train $2$ can safely depart?

c$)$ If Train $1$ starts at $8$:$00$ and Train $2$ starts at $9$:$00,$ list all the times that Train $3$ can safely

depart?

Question $2$: $[$CSP Formulation$]$

Formulate the train scheduling problem as a constraint satisfaction problem $($CSP$)$ by

providing each of the following:

a$)$ What are the variables for this problem? Denote those variables by x$1,$ x$2...$

b$)$ What is the domain of each variable? Use the original definition without eliminating any

values.

c$)$ Provide a complete list of constraints using precise mathematical notation. For example,

you may say that x$1+2!=$ x$2,$ where x$1$ and x$2$ are CSP variables. $($Hint: You should express

all your constraints using

Question $3$: $[$Backtracking Search$]$

Based on your formulation in Question $2$ above, answer each of the following:

a$)$ Selecting variables in the order: Train $1,$ Train $2,$ Train $3,$ Train $4,$ Train $5$ and selecting

values to assign in the order: $8$:$00,9$:$00,10$:$00,$ draw the entire search tree that is

generated by the Backtracking Search algorithm until a successful complete assignment is

found. How many nodes are generated? $($Hint: many nodes are generated$)$

b$)$ Suppose variables are selected in different order as in: Train $4,$ Train $1,$ Train $2,$ Train $3,$

Train $5,$ but with the same order of values, $8$:$00,9$:$00,10$:$00.$ Draw the entiresearch tree

that is generated by the Backtracking Search algorithm until a successful complete

assignment is found. Now, how many nodes are generated? $($Hint: a few nodes are

generated$)$

c$)$ Compare your answers to $3($a$)$ with $3($b$).$ What do you observe? Does the order of

selecting variables and values matter in the Backtracking Search algorithm?

Question $4$: $[$Consistency Checks$]$

As described in the lecture, there are many consistency checks that can be implement before

we start the Backtracking Search algorithm. The objective of these consistency checks is to

reduce the search space. Explore some of these:

a$)$ In your CSP formulation in $(2),$ you should have some unary constraints. Use these to

prune the domains of the concerned variables and list the updated domains.

b$)$ Draw the Constraints Graph based on your results in $($a$)$ above and apply Arc Consistency

on the graph to further prune the domains of the variables. List the updated domains.

Question $5$: $[$Variable and Value Ordering$]$

As noted in question $(3),$ the order of variables and values isan important factor that determines

how efficient the Backtracking Search algorithm is$.$ To explore this, answer the following::

a$)$ Using the Minimum$-$Remaining$-$Value $($MRV$)$ heuristic, explain why it is best to start with

Train $4.$

b$)$ Having started with Train $4,$ use the Degree heuristic to explain why it is best to use Train $1$

next.

Question $6$: $[$Programming$]$

Based on your updated domains in question $4($b$),$ write a Python program using the PythonConstraint library $($similar to the examples given to you$)$ to solve this problem.

Note: You need to attach the source code and a screen$-$short of your output.