A major challenges in modeling vehicle routing problems is the formulation of constraints that prevent short-cycles (roundtrips not including the depot node 0). Beside the con- straints you know from the lecture slides there are several different ideas for the formu- lation of short-cycle-prevention constraints. In the following, we investigate the Miller- Tucker-Zemlin-contraints (b) for the prevention of short-cycles. In this context, we use the following symbols N: number of customer locations that require a visit (Attention: the depot has the number 0!) K: number of available vehicles Dijk: binary decision variable, which is equal to 1 if and only if vehicle k drives directly from node i to nodej : non-negative and continuous decision variable for the combination of customer location i and vehicle k. It indicates the position of node i in the visiting sequence decided for vehicle k . (1) tek - + N24 SN-1 Vij {1,...,N} Vk {1,..., K} Assume that we have a vehicle routing problem with exactly one vehicle (K = 1). Figure 2: Locations of a vehicle routing problems to be served by one vehicle) (a) Draw a least distance round trip through all five nodes into Fig. The travel distances correspondig to the distances in the figure. (4 points) (b) Specify all restrictions of type (b) for the here investigated vehicle routing problem. (16 points) 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. (e) Is it possible that the here investigated vehicle routing problem has exactly one optimal solution? Justify your answer! (1 point)