代做CSC 4120、代写Python程序语言

日期：2024-05-19 07:54

CSC 4120 Project

Party Together

March 17, 2024 Version 1.1

1 Problem Statement

You and your friends are going to have a party at your house this weekend to celebrate the

end of the semester. You, being an excellent driver with a nice car, offer to pick up all

your friends near or at their homes and drive them to your house. Can you come up with a

transportation plan so that everyone gets to the party as efffciently as possible?

Formally, you are given an instance of the Party Together Problem (PTP) with inputs

(G, H, α). G = (V, E) is an undirected graph where V is the set of nodes indexed from 0 to

|V | − 1 and each node represents a location in the city. The weight of each edge (u, v) is the

length of the direct road connection between location u and v, which is non-negative. Your

house is at location 0. H ⊂ V is the set of distinct locations that correspond to your friends’

homes. If F = {0, 1, . . . , |F| − 1} is the set of friends, then each friend m ∈ F has a house

location hm ∈ H and each house location corresponds to exactly one friend. The constant α

refers to the relative cost of driving vs walking.

A possible pickup schedule speciffes the locations where you will pick up your friends.

More speciffcally, it will specify for each friend m a pickup location pm ∈ V , and you will

need to drive your car starting from your home to pass from all the pickup locations to collect

your friends and bring them back home (assume that the car has enough capacity to carry

all your friends).

Cost structure: Each friend incurs a walking cost equal to the distance traveled to get

from his home to his pickup location. You incur a driving cost equal to the distance traveled

by your car multiplied by the constant α, 0 ≤ α ≤ 1. It is in general more efffcient to travel

by car than walking, and the cost of the car does not depend on how many people it carries.

Assumptions:

• The capacity of your car is unlimited.

• Your friend would take the shortest path from her home to her pick-up location.

• You can pick up multiple friends at the same location.

• You may pass from the same location more than once.

• The graph is connected.

• There is no road from a location to itself, i.e., there is no edge (i,i) in the graph for

any i.

1• Triangle inequality holds. Taking the direct path between two locations (if it exists)

is always not longer than going through some other intermediate location, i.e., for any

edge (i, j) in the graph and any location u ̸= i, j,

wij ≤ diu + duj

,

where dxy is the length of the shortest path from location x to location y.

Your task is to ffnd i) the set of pick-up locations for your friends, and ii) a routing

schedule of the car, i.e., a ‘tour’

1

that includes node 0 and the above pickup locations, that

minimize the total cost.

The total cost is calculated as follows. Let L = {pm}m∈F be the set of locations you

pick up your friends, and {u0, u1, · · · , un}, u0 = un = 0, be the tour of the car where

L ⊆ {u0, . . . , un−1}. Let dij be the length of the shortest path between locations i and j.

The total cost corresponding to this tour and set of pickup locations is

α

Xn

i=1

wui−1ui +

|F

X

|−1

m=0

dpmhm.

For the example in Figure 1 where H = {1, 2, 3} and α =

2

3

, the optimal car tour is

0 → 1 → 0 and pick up everyone at node 1. The total cost is (2 ∗

2

3 + 1 + 1 =

10

3

).

Figure 1: Example: Graph G, H = {1, 2, 3}, α =

2

3

. Optimal car tour colored in red, friend

walking tour in blue, everyone get picked up at node 1. Total cost is

10

3

.

Project Deliverables The project is divided into four parts. In the ffrst part, you have to

generate inputs for the problem. In the second part, you have to implement a solver solving

the problem. In the third part, you would consider a simpler version and practice dynamic

programming. In the last part, you will look at theoretical aspects of the problem.

2 Input Generation

Overview In this part, you will have to generate inputs for the problem, that is, create

instances of the problem. We would gather everyone’s inputs and test your solver in Question

1A path is sequence of nodes where any two consecutive nodes are connected with an edge. A tour is a

path that start and ends in the same node and can repeat nodes. A simple tour (or simple cycle) is a tour

that does not repeat nodes.

23 on them. You might like to design inputs whose solution is hard to ffnd so only your group

can perform well in the test. To do this, you may ffrst think of possible approaches to solve

the problem and then design inputs to induce the algorithm to bad solutions.

Input Format The ffrst line of the input ffle would be a ffoat number α representing the

relative cost of driving vs walking.

The second line of the input ffle contains two integers |V | and |H|, separated by spaces,

where |V | is the number of nodes in the graph and |H| is the number of homes (friends).

The nodes will be indexed from 0 to |V | − 1.

The third line contains the list of home nodes, separated by spaces.

The following lines have similar structures which specify the adjacency list of the graph.

The ffrst label in a line is the source node index followed by the node degree d. The next

d lines are target node indices and integer edge weight. That pattern repeats for all nodes in

the graph.

Sample Input: consider the example in Figure 1, the corresponding input ffle would be

0.6666667

4 3

1 2 3

0 1

1 1

1 3

0 1

2 1

3 1

2 1

1 1

3 1

1 1

Question 2 Generate 4 inputs with different sizes and α in the required format. Your

graphs must be connected and satisfy the triangle inequality. You will generate 1 input for

each of the following problem categories:

• α = 0.3, up to 20 nodes and 10 friends

• α = 1.0, up to 20 nodes and 10 friends

• α = 0.3, up to 40 nodes and 20 friends

• α = 1.0, up to 40 nodes and 20 friends

Name them 20 03.in, 20 10.in, 40 03.in, 40 10.in, respectively.

3 Solve PTP

Overview In this part, you are asked to solve the PTP problem. We know this is demanding,

so we give you some hints (actually, possible solutions!) to start with.

3Question 3 In ptp solver.py ffle, implement the function ptp solver(G, H, α) to solve PTP,

where inputs are the graph G, home list H, and coefffcient α. You should return a list of

nodes traversed by the car as well as a list of pick-up locations. More instructions would be

given later in this documentation and in the python ffle.

Your solution must not be the same as in Question 4.2.

You are encouraged to do some research to ffnd similar problems and algorithms to solve

them. You can do reductions or/and use the ideas from the solutions. We give you some

keywords here: travelling salesman (subset tour) problem, shortest paths visiting speciffed

nodes problem, vehicle routing problem...

In case you are struggling to come up with a solution, we provide two possible approaches

here:

1. Integer Linear Program (ILP). You can model the problem as an ILP and call a solver

to solve it. You can check Miller’s paper on 1960 [1] where they formulated TSP as an

ILP to get an idea. In Zhang et al (2023)’s paper [2], the authors optimize ride-hailing

vehicle routing problem with vehicle-customer coordination where customers can walk

to the pick-up locations in an Euclidean space with speed and time constraints.

2. Greedy algorithm with insert/delete heuristic. In [3], the authors proposed an insert/delete

heuristic to solve the travelling salesman subset-tour problem where the

salesman has to visit a subset of nodes of the graph with constraints. Here in our

problem, we can take the heuristic to build the solution iteratively.

Note that once we have a tour T of the car, the pick-up locations are implicitly deffned

since we would let friends take the shortest path from their homes (if not already in

the tour) to the tour. The cost c(T) of a (feasible) solution based on T is the sum of α

times the total length of the tour and the total walking distance of friends. Therefore,

we seek to ffnd a T with minimum c(T). The only requirement of T is that it must be

tour starting and ending in node 0.

The heuristic algorithm 1 (see pseudocode below) works in following way. We start

with an arbitrary tour T and do a local search to improve the total cost. At every

step, we change T by either deleting a node from T or adding a new node to T in a

way to reduce c(T) the most. Stop when there is no further improvement that can be

made. Since triangle inequality holds, the total number of changes would be linear in

|V | (take it as granted).

Hint: You may want to consider precomputing the all-pair shortest path distances, so

you have them ready when executing your algorithm.

4 A Constrained Version

Overview In this part, we consider a simpler version of PTP, namely Pickup from Home

Problem (PHP). The problem has the additional constraint that you must pick up your

friends at their homes (so we don’t need to worry about optimizing over the set of pickup

locations).

It is easy to establish NP-hardness of PHP by reducing the Metric Travelling Salesman

Problem (M-TSP) to PHP. M-TSP is deffned in terms of a graph Ge = (Ve, Ee) that is

4Algorithm 1 PTP Algorithm with Insert/Delete Heuristic

T

1 ← {0}

n = |V | ▷ Number of nodes

for k = 1, 2, · · · do

for i = 1, 2, · · · , n do ▷ Compute one node change of T

k

if i ∈ T

k

then

T

k

i = T

k

.remove(i) ▷ Directly remove

else

T

k

i = T

k

.least cost insert(i)

▷ Multiple places to insert. When connecting to a node in the tour use the

shortest path to that node. Take the one with minimum c(T)

end if

end for

i

k = argmini c(T

k

i

)

if c(T

k

) ≤ c(T

k

i

k ) then

Break

else

T

k+1 = T

k

i

k

end if

end for

complete (there is an edge between any two nodes) and triangle inequality holds

2

. It requires

to ffnd a tour with minimum total length that is simple (does not repeat nodes). For any

instance Ge = (Ve, Ee) of M-TSP, we can construct an instance of PHP with V = Ve, E = Ee,

where V corresponds to set of the home locations of the party owner and his friends. In this

special case of PHP all nodes correspond to home locations and are fully connected with

edges.

In the optimal solution of such a PHP instance, each node is visited exactly once: First,

we have to visit each node and the solution decides in which order we visit the nodes. Second,

no node would be visited more than once since i) the edge weights are nonnegative, ii) the

graph is complete, and iii) triangle inequality holds (hence, we can improve the cost if there

are loops by taking shortcuts, check it!). Therefore, the solution of PHP is the solution of

M-TSP. The transformation is clearly in polynomial time. This completes the reduction.

Since M-TSP is known to be NP-hard, so is PHP.

On the other hand, we can reduce PHP to M-TSP. That is, for any instance of PHP,

we can transform it to an instance of M-TSP. After getting the solution of TSP from some

oracle (which we don’t care for now) we can transform it back to the solution of PHP. Then,

if we know how to solve TSP, we know how to solve PHP. The transformation can be done

in polynomial time by following procedure.

1. Given an instance (G = (V, E), H) of PHP, construct a complete graph G′ = (V

′

, E

′

)

where V

′ = H ∪ {0}. For every edge (u, v) ∈ E

′

, the weight of the edge is the distance

of the shortest path from u to v in G.

2

In class we introduced Euclidean TSP where nodes correspond to locations on the map and edge weights

correspond to Euclidean distances, hence, triangle inequality holds. Here we consider a more general graph

where distances are not necessary Euclidean but triangle inequality still holds

52. Solve M-TSP on G′

to get the tour C

′

. Note that G′

is complete and triangle inequality

holds. We introduced a dynamic programming solution to such TSP in lectures.

3. Given C

′

, construct the optimal tour C for PHP by substituting the edges in C

′ with

the corresponding shortest paths in G.

Question 4.1 In mtsp dp.py file, implement the function mtsp dp(G) to solve M-TSP using

dynamic programming algorithm introduced in the lectures, where input is a complete graph

G with triangle inequality.

If you don’t have time to write the DP algorithm, you can call an auxiliary solver to solve

TSP but you will get 60% deduction for this problem.

Question 4.2 In pthp from tsp.py file, implement the function pthp solver from tsp(G, H)

to solve PHP, where inputs are graph G and home list H and output is a list of nodes

traversed by the car. You must use the reduction above and solve TSP using Question 4.1.

5 Theoretical Questions

Overview In this part, we look into theoretical aspects of the problem including NPhardness

of PTP and approximation ratio of PHP.

Clearly, solving PHP on the same graph gives a feasible solution to PTP. The question is,

is it optimal? If not, then how bad can it be?

Question 5.1 Show that PTP is NP-hard.

Hint: Are there values for α for which PHP = PTP (the solution of PHP is obtained by

solving PTP)? Since PHP is NP-hard, then PTP is also NP-hard.

In general, we would expect PHP to give a sub-optimal solution for PTP since we don’t take

the choice of pick-up locations into the optimization. That is to say, in any instance (G, H, α)

of the PTP, let Cphp and Cptpopt be the total cost of the solution obtained from solving PHP

(G, H) and the optimal solution of PTP, respectively. Define β =

Cphp

Cptpopt

. Clearly, β ≥ 1. We

are interested to know how bad β can become if an adversary is free to choose the parameters

of the problem.

Question 5.2 Show that the cost of PHP is at most twice of that of the optimal solution

(which we don’t know). That is, β =

Cphp

Cptpopt

≤ 2. Also show that this bound is tight, i.e.,

there is an instance where β = 2 (at least asymptotically). You can assume α = 1 for

simplicity.

66 Input & Output Format

6.1 Graph Representation

We would use Python package NetworkX to store graphs throughout the project. NetworkX

is a very powerful and useful tool to networks studies. It’s convenient to modify your graphs

such as adding attributes with NetworkX. Install the package here. And check this tutorial

to get a quick start. You can find more examples in the handout codes of week 7 and week

8.

We will handle input operations and graph constructions for you. We define the API of

the functions you should implement which you must obey. The I/O definitions can be found

in corresponding question descriptions, section 5.3, and python file comments.

But for your information, and in case you wish to use other representations, which is

totally okay if you modify the template correspondingly and submit all your codes so we can

reproduce your work, we present formats of input files below.

6.2 Input File Format

The first line of the input file would be a float number α representing the relative cost of

driving vs walking.

The second line of the input file contains two integers |V | and |H| separated by spaces,

where |V | is the number of nodes in the graph and |H| is the number of homes (friends).

The nodes will be indexed from 0 to |V | − 1.

The third line contains the list of home nodes, separated by spaces.

The following lines have similar structures which specify the adjacency list of the graph.

The first label in a line is the source node index followed by the node degree d. The next

d lines are target node indices and integer edge weight. That pattern repeats for all nodes in

the graph.

Sample Input: consider the example in Figure 1, the corresponding input file would be

0.6666667

4 3

1 2 3

0 1

1 1

1 3

0 1

2 1

3 1

2 1

1 1

3 1

1 1

76.3 Function APIs

6.3.1 PTP Solver

You are encouraged to come up with different algorithms to solve PTP and compare them.

We’d like you to gradually improve your algorithm. PTHP solver would be a good start

point since you can take pick-up locations into consideration to achieve lower cost as well as

use heuristics to gain solutions faster. At last, we would only evaluate your solver in function

ptp solver as in Question 3. So put your best algorithm there. PTP solvers would have

following API.

Input: NetworkX graph G, a list H of home nodes in indices, a float number α ∈ (0, 1]

representing the unhappiness of people one the car per unit of road travelled.

Output: τ , L where τ is the list of indices of the nodes traversed by your car and L is an

iterator of (pick-up-locations, people-picked-up) pairs. People would be represented by the

index of her home node. Again, your output should legitimate. The indices must be in the

graph, i.e., integers from 0 to |V | − 1. The tour τ must begin and end at node 0. It can

only go through edges that exist in the graph. The pick-up locations must be in τ . Everyone

should get picked up.

A sample out of the example in Figure 1 would be

\ tau = [0 , 1 , 0]

L = {1: (1 , 2 , 3) }

return \ tau , L

6.3.2 M-TSP Solver

You will implement one solver to solve TSP on a metric graph using dynamic programming

algorithm in Question 4.1.

Input: NetworkX graph G.

Output: a list of indices of the nodes traversed by the car. The tour must visit each node

exactly once. It must begin and end at node 0.

6.3.3 PHP Solver

Essentially, you only need to implement one PHP solver, namely pthp solver from tsp in

Question 4.2.

Input: NetworkX graph G and a list H of home nodes in indices.

Output: A list of indices of the nodes traversed by your car. The output must be

legitimate. The indices must be in the graph, i.e., integers from 0 to |V | − 1. The tour

must begin and end at node 0. It can only go through edges that exist in the graph. It must

visit every node in H.

6.4 PTP Output File Format

We would store your output for PTP in a file so you can analyze it. The output file corresponding

to an input file would have the same name, except with the extension replaced by

“.out”. For example, the output file for “1.in” would be “1.out”.

8The first line of the output file would be a list of nodes represent the tour taken by the

car, separated by spaces. The nodes would be in the order in which they are visited by the

car. The list would start and end at node 0.

The second line would be an integer d represents the number of pick-up locations.

For the following d lines, each line starts with a node index followed by a list of picked up

friends, separated by spaces. Your friends are represented by the index of their home nodes.

Sample Output File consider the example in Figure 1, the corresponding output file

would be

0 1 0

1

1 1 2 3

7 Submission & Evaluation

Overview You are encouraged to work in group as working collaboratively is a skill in and

of itself. It will also reduce your workload for this demanding project. Only one member of

the group needs to submit your solutions to bb. The deadline is 23:59, May 19th, 2024.

Evaluation The total point of the project is 100, which is worth 10% of your final grade.

You will earn these points as follows.

• 10pts for Question 2.

• 20pts for Question 3.

• 10pts for Question 4.1.

• 10pts for Question 4.2.

• 10pts for Question 5.1.

• 10pts for Question 5.2

• 20pts for proposing a good PTP solver. We will test your PTP solver on all inputs

generated by the students. We would calculate the average cost of your solver. You

would be scored based on the average cost compared to that of other teams. The score

will range from 0 to 20 based on the following:

– 20pts: your solution performs better than 80% of student submissions.

– 16pts: your solution performs better than 60-80% of student submissions.

– 12pts: your solution performs better than 40-60% of student submissions.

– 8pts: your solution performs better than 20-49% of student submissions.

– 4pts: your solution performs better than 0-20% of student submissions.

• 10pts for the report.

9Submission Details Each group should submit four things: inputs, outputs, codes, report.

We will provide you a series of input files. You should run your algorithms in each of them.

You need to submit your output for every input provided with correct file names. Put

the outputs in a separate folder. You also need to submit your codes for solving PTHP

and PTP. In part of those, you need to write a report containing solutions to the theoretical

questions 5.1, 5.2 and approaches you take to solve PTP. For each of the approaches you

take, write no more than one page to describe how it works and how it performs. Your report

should be in pdf form.

Zip everything into one file and name it with your group ID. A typical submission

would have a minimal structure as follows.

group 0

inputs

20 03.in

20 10.in

40 03.in

40 10.in

outputs

1.out

2.out

...

ptp solver.py

mtsp dp.py

pthp solver from tsp.py

report.pdf

8 Specifications of the Usage of Libraries

You can use any existing packages and solvers. But you have to make sure we can reproduce

your work.

9 Academic Honesty

In completing this project, students are expected to adhere to principles of academic honesty.

All work submitted must be original and created solely by the individual student or group,

unless otherwise specified. Proper citation of sources is required to give credit to the ideas

and work of others. Any form of plagiarism, cheating, or dishonesty will result in disciplinary

action, which may include a failing grade for the project or course and report to the school.

10References

[1] C. E. Miller, A. W. Tucker, and R. A. Zemlin, “Integer programming formulation of

traveling salesman problems,” J. ACM, vol. 7, no. 4, pp. 326–329, 1960. doi: 10.1145/

321043.321046.

[2] W. Zhang, A. Jacquillat, K. Wang, and S. Wang, “Routing optimization with vehicle–customer

coordination,” Management Science, vol. 69, no. 11, pp. 6876–6897, 2023.

doi: https://doi.org/10.1287/mnsc.2023.4739.

[3] J. Mittenthal and C. E. Noon, “An insert/delete heuristic for the travelling salesman

subset-tour problem with one additional constraint,” The Journal of the Operational

Research Society, vol. 43, no. 3, pp. 277–283, 1992. doi: 10.2307/2583718.

11