Description

DING Yukuan
18082849d FAN Jiaqi 18081491d LI Jinlin 18081569d ZHANG Caiqi
18085481d
Question 1: Formulate the problem
Graph Demo

Explication
• node(i) : node(1) represents 7:00 p.m., node(2) represent 8:00 p.m., and so on.
• edge{i,j}: Hire a driver, who drive from time i to j. Its weight is the cost of driver.
• Noted that if the driver only works part of his driving time, we also give him full payment.
• Under this formulation, the question becomes to a shortest path problem.
1
Question 2
In our program, we name time 7 : 00,8 : 00,…,2 : 00 to node 1,2,…,8. The full version of the code is attached in the zip file named Lab1AssignmentCodes.py. Here is the main part.

import networkx as nx import matplotlib.pylab as plt
G = nx.Graph()
# Add nodes
G.add_node(1)
G.add_node(2)
G.add_node(3)
G.add_node(4)
G.add_node(5)
G.add_node(6)
G.add_node(7)
G.add_node(8)
# Add edge
G.add_edges_from([(1, 5), (2, 6), (3, 7)], weight=50)
G.add_edges_from([(1, 4), (2, 5), (3, 6), (4, 7), (5, 8), (6, 8), (7, 8)], weight=40)
G.add_edges_from([(1, 3), (2, 4), (3, 5), (4, 6), (5, 7), (6, 8), (7, 8)], weight=30)
# The start time is 7:00pm, denoted as node 1
# The end time is 2:00am, denoted as node 8
# Find the the shortest path from node 1 to node 8 print(nx. shortest_path (G, 1, 8, weight=’weight’)) print(nx .shortest_path_length(G, 1, 8, weight=’weight’) )

The shortest path is [1,5,8], and the length is 90.
Question 3
We know that the shortest path is [1,5,8], and cost is 50$ + 40$ = 90$.
The length of the shortest path represents the minimum cost of hiring the drivers, which in this case is 90 dollars.
The nodes in the shortest path indicate how to hire the drivers. In this case, it means that we should hire a regular driver at 7:00 pm. After that, we should hire a part time driver from 12:00 pm to 2:00 am (3 hours).
2