ECE4530J Homework 3-Solved

Problem 1
Consider the undirected network in the figure below. A vehicle wants to travel from node 1 to node 4. Suppose that every link has a length of 𝑙. We want to find the shortest path (SP) through linear programming.

a)         Define the decision variables for the SP problem.

b)        Define the objective function for the SP problem.

c)         Formulate the SP problem; you need to write and explain every constraint. You should either write out all constraints (this is possible because of the small size of the network) or clearly define any generic indices you use.

Problem 2
Consider the undirected network in the figure below. Links (1,2), (2,3), (3,4) are highways with a

capacity of 6000 veh/hr and a travel time of 3 min. Links (1,3), (2,4) are local streets with a capacity of 3000 veh/hr and a travel time of 10 min. The traffic demand is indicated in the figure as well (unit: veh/hr). We want to allocate the traffic flows to minimize the average travel time for all vehicles.

a)         Define the decision variables for flow optimization.

b)        Define the objective function for flow optimization.

c)         Formulate the flow optimization problem; you need to write and explain every constraint. You should either write out all constraints (this is possible because of the small size of the network) or clearly define any generic indices you use.

d)        Now, suppose that every vehicle entering the network at node 1 (resp. 2) must exit through node 3 (resp. 4). Formulate the flow optimization problem under this additional constraint. Hint: You need to modify the decision variables.

Problem 3
Consider the trajectory planning problem in the figure below. An autonomous vehicle is initially stopping at the origin, facing east, and is supposed to arrive at the destination no later than 120 sec with any orientation. The vehicle cannot get out of the 15-by-25 rectangle. The magnitude of the vehicle’s acceleration (resp. angular acceleration) cannot exceed 𝑎̅ m/s2 (resp. 𝜙̅ rad/s2). We consider a DT formulation with a step size of 1 s.

a)         Define the absolute position and orientation of the vehicle.

b)        Formulate the objective function.

c)         Formulate the constraints.

d)        Suppose that 𝜙̅ = 𝜋 rad/s2. Give a value for 𝑎̅ such that the problem is feasible, and construct a feasible solution. Give another value for 𝑎̅ such that the problem is infeasible, and explain why it leads to infeasibility.

e)         [Bonus] Suppose that 𝜙̅ = 𝜋/4 rad/s2. Give a value for 𝑎̅ such that the problem is feasible, and construct a feasible solution.