Bonus Project: Travel Planning

Bonus Project: Travel Planning

1.Project Objective:
Apply the knowledge learned from the course of data structures and implement an efficient and effective travel planning application.

2.Project Description:
You are to apply the traveling salesman algorithm to develop a travel planning application. The goal is to earn the most happiness credit while the total traveling time is within allowed quota.

 The specification of the graph is described below:
a.The graph is a simple undirected graph with at most 100 nodes and no more than one edge between any two nodes.
b.Node’s name should be a string of fewer than FOUR characters.
c.Each edge has tagged a weight indicating the traveling time measured in minutes required to move from one end to the other end of the edge.
d.Each node has tagged a weight indicating the happiness index of the node.
e.Each node is further tagged an opening business time and closing time.
f.The business opening and closing hours are integer numbers (0 ~ 2147483647) indicating the time in minute relative to midnight (00:00). Therefore, 08:00 in the morning will be represented as the value of 480.
g.The weight of each edge or node is an integer between 0 ~ 2147483647.

 Your traveling plan should follow these rules:
a.Always start from the first node on your data list.
b.Always end at the first node where you start.
c.For each node visited, no matter how many times, you earn its happiness credit only once to your total happiness measure.

3.Two Sub-Problems:
Both sub-problems are to plan the best trip maximizing the total earned happiness credit assuming that
(1)The business hours are ignored. In other words, each node can be visited any time.
(2)You earn happiness credit only if the node visited is open for business. However, you may pass through a node which is not in business without earning happiness credit. Additionally, you can wait until a node is open for visit.

You may choose to complete only one sub-problem.

3.Test Case:
Every student has to design and submit a test case prepared as a text file, named “tp.data.”

For the test case, the first line contains four numbers: the number of nodes (n), the number of edges (m), the quota of traveling time (t) (in a minute) and traveling start time (b) measured in minute relative to midnight. After the first line, there shall be n lines, and each line shall contain the node’s name and the happiness index (h) of the node and two integers, one for the node’s business opening time and one for closing time. After that, there shall be m lines, and each describes the information of an edge. Each edge information line contains three fields, name of node one, the name of node two, and the weight of the edge.

Example
2 1 100 480
TPE 3 720 900
NTHU 4 0 1440
TPE NTHU 50

This case describes a graph with two nodes. The quota of total traveling time is 100 minutes and the time to start traveling is 08:00 (or 480 minutes after midnight). Node “TPE” is open between 12:00 ~ 15:00 and node “NTHU” is open all day. The traveling time between “TPE” and “NTHU” is 50 minutes.

4.Valid Test Case
a.Make sure that there exists a path between every node pair.
b.The node business closing time should always be after the opening time.

5.Test Case Competition
TAs will use all test cases collected from the class to evaluate your algorithm.

6.Result output file
Output the answer for sub-problem 1 in “ans1.txt” and sub-problem 2 in “ans2.txt”.
The first line is the total happiness credit earned of your traveling plan and the total time used for this trip. Then, you shall list nodes visited in the order visited and each visited node’s name is followed with two integer numbers, the arriving time and the leaving time. For the last node visited in the trip, the leaving time shall be the same as the arriving time.

c.Example:
7 100
TPE 480 480
NTHU 530 530
TPE 580 580

Note: The node “TPE” is visited twice, but you earn the happiness credit of “TPE” once.

d.Example:
3 0
TPE 480 480

  Note: you do nothing and earn only the minimum happiness.

7.Project Submission Rules
e.Submit your test cases and program to LMS following the set deadline.
f.Allow no second submission.

8.Grading Policy
g.Algorithm Quality (80%)
·Each sub-problem (40%)
Your implementation quality will be evaluated according to the following formula. For each test case j, we compute the numbers of wins of happiness credit  earned for a person i. Simply, if your program achieves higher happiness credit than w other people, then the number of wins is w. The quality score for a person i is then calculated as the following. Note that the total allowed execution time is restricted to be less than 30 seconds.
Total happiness quality score:
·Failed implementation receives zero scores: If your program cannot compile or execute on our testing platform, you get no score. Also, you should use only standard C++11 library, and should not use assembly codes. Note that our testing platform is a simple machine which supports only standard CPUs, supports no GPU, nor other non-CPU instructions, and is not connected to the internet.

h.Test cases (20%)
Your test case is to be measured according to how well it can differentiate good algorithms from bad algorithms in the following formula,
,
where N is the number of students,  is the earned happiness credit of the i-th student’s program and  is the best result. We will use your implementation of sub-problem 1 for this evaluation.
·Illegal test case receives zero scores.
Note: if your project cannot pass through your test case, you will receive zero scores for the whole project.

Etiquette
a.Do not plagiarize others’ work, or you will fail this course.
b.Late homework will not be accepted.
c.Please frequently check the class website announcements for possible updates.