The Time Window Model and Shortest Path Model Design for Travel All 5A Scenic Spot in China
Yawei Li, Yandong Li, Xiaorong Li
Graduate School, Beijing Wuzi University, Beijing, China
To cite this article:
Yawei Li, Yandong Li, Xiaorong Li. The Time Window Model and Shortest Path Model Design for Travel All 5A Scenic Spot in China. American Journal of Applied Mathematics. Vol. 4, No. 4, 2016, pp. 192-196. doi: 10.11648/j.ajam.20160404.15
Received: June 28, 2016; Accepted: July 8, 2016; Published: August 2, 2016
Abstract: Travel has became one of the most popular ways of modern lifestyle. This paper mainly discusses the route planning of travel all 5A scenic spots in the China. Firstly, We establish a mathematical model and transform the limited conditions include the scenic tour time, driving time, accommodation and other aspects to the mathematical formulas. Then, we introduce the relevant variables from the basic formula and draw the flow chart of the algorithm. In some places that densely-scenic spot, we use the "postman problem" to give the solution and specific analysis some places according to the specific conditions. Specifically, according to the seven regions of the country, we find the best path. In the same area, according to the specific circumstances such as the time and route of the integration, while considering the requirements of the subject like visit time and proportion of driving time, we plan to visit scenic spots one provine by province In order to improve the utilization rate of the time, we arrange the tour attractions in different regions in one year, let the vistor feel the difference between different areas of the landscape, fully enjoy the great rivers and mountains of the motherland, enhance the overall quality of tour.
Keywords: Optimal Path Planning, Multiple Time Windows, Chinese Postman Problem
1. Background of Problem
With the improvement of people's living standards, tourism has become one of the activities that people love, and it is becoming one of the important driving force for the development of the global economy. More and more people like to travel the scenic spots and historical sites or famous mountains and great rivers to relax their body and mind, improve their self-cultivation on a holiday.
A self driving travel enthusiasts plan to travel the all 201 5A level scenic spots to be released by the National Tourism Administration. The travel time of this enthusiasts every year not more than 30 days, the number of trips per year is not more than 4 times, each time not more than 15 days. At the same time, according to the degree of interest, determine the minimum tour time in each 5A scenic spots. The travel enthusiasts based on safety considerations, travel time is also set to 7:00 to 19:00 per day, every day is not more than 8 hours of driving time. In order to ensure the quality of the tour and physical problems, in the daily schedule, if visit in all day, the driving time need under 3 hours; if visit a half day driving time control within 5 hours. The average speed of driving on the highway is 90 km / h, and the average speed is 40 km / h on the average road. The plan of the tourist lovers in every capital city to stay for at least 24 hours, to arrange a time to visit the city characteristic construction and experience local customs (not arrange scenic view). The opening time of the scenic spot is unified to 8:00 to 18:00.
2. Analysis of the Problem
The topic background can be considered as a path problem with time windows. The topic has the earliest opening time and the closeing time of the scenic spot. Under these restrictions, in addition to the spatial aspects of the path to consider, also have to add time scheduling considerations. At the same time, due to the time window of the driving car, also led to the limitation of the length of the path problem, so we not only need contains the cost of the way, but also have to consider the time cost. Therefore, the discussion of time and space is very important.
In the course of analysis the problem, firstly we consider the limiting conditions are given in the subject, according to the time window of travel to establish a model. In the route planning, we take the regional approach, travel the spots that distance close, or add some scattered spots to try to make the total travel time is close to 30 days. And then according to the number of days each tourist trip, arrangement and combination, to achieve the minimum number of total travel days. The different regions of the attractions travel in a year help to enhance the experience of tour.
3. Self Driving Tour of Travel Route Planning
3.1. Model Assumptions and Symbolic Description
3.1.1. Model Assumptions
1. All of the links between the provinces and cities can be passed smoothly, there will be no traffic jams, etc.;
2. We do not take into account changes in the weather, tourists sick and other unexpected situation;
3. The speed of the car to maintain constant speed unchanged;
4. Some scenic spots need to visit in one day and can accommodation in the scenic spots area can be divided into two half day tour, such as Chengde Mountain Resort scenic spots, Mountain Resort and the surrounding temples can be separated from the tour.
5. This design don’t reflect the time about traveller dining and going to the toilet, the default in driving, traveling or accommodation time to solve those problem.
3.1.2. Symbol Description
: The travel enthusiasts i times travel in one year;
: The days needed in i times travel in one year;
: The highway mileages in d times driving, according to the route of each trip and reference attachment, the unit is kilometers;
: The non highway mileage in d times driving, according to each travel route and refer to the attachment that, the unit is km (including the city to the county of non high speed mileage and city or county to the scenic tourist line).
: The time required by the travel enthusiast to drive the car in d day;
: The average speed of driving on the highway is 90 km/h;
: The average speed of driving on a non highway is 40 km/h;
: the moment of The tourist's d day, the 24 hour system;
: The average speed of the time T in the d day, the unit is km/h;
: The distance of highway From departure to destination;
: The distance of non highway From departure to destination;
: The time required for visit some scenic area, the value of 4 or 8;
: The highway has not been completed in d day, it needs to go on in d+1 day.
: The non highway has not been completed in d day, it needs to go on in d+1 day.
3.2. Establish the Model
3.2.1. Constraint Condition of the Model
According to the problem, the constraints are listed as follows, When or ,, that is the driving time between 7:00—19:00.
3.2.2. Analysis Model Method
Situation one: can reach the destination within one day.
1. The distance from the departure and destination:
When , the day can reach the scenic spot, ,.
2. After reach the scenic spot, when , or when ,, we can continue to judge. To judge the time and the time needed to play the scenic spot:
When , we can end the scenic spots, ready to go to the next destination. Prior to this, still have to judge the distance from the departure to the destination: .
When , it’s mean the visitor can not reach the next scenic spot, the choice is accommodation in this scenic spots.
Situation two: the starting point of a day can not reach the destination.
1. Determine the departure to the destination: Then one day is not able to reach the destination.
When ,, In the premise of ensuring that there can be accommodation to make the day travel distance most likely to execute close to 720, At this time the distance to reach the destination is still far away:
2. Determine the time to travel these distances
The time required to travel these distances is: .
When , the visitor can arrive before 8 o'clock and visit scenic spots in a day (the scenic spots need to play two days can choose to live in the area and continue to play the next day), then we can go down to a destination.
When , The time to reach the scenic spot is: 7+, and:
(1) If M=4, and
Visitor Can end the play of this scenic spot.
Visitor Can not continue to play scenic spots, should stay in the scenic area and change to the next morning 8:00 play.
(2) If M=8, and
Visitor Can end the play of this scenic spot
Visitor can not continue to play the scenic area, should stay in the scenic area and change to the next morning to continue to play 8:00.
If , then the visitor can lived in the area, the time that next day to continue to play the scenic area: .
Then visitor go to the next destination.
To judge the distance between the starting and destination circulatly and get the maximum value of each trip. The result obtained by this method is the feasible solution under certain conditions, and it is not the optimal solution.
3.2.3. Flow Chart of Model Algorithm
3.3. Model Solving and Route Planning
According to the established model and the information provided in the attach, through access to information collection involved between provinces mileage to divide the area into modules, uphold the principle of concentrated spots together travel, scatter spots combination travel, introduce the "a pen to draw" and "Chinese postman problem"to design a reasonable route, see in the table below:
|years||scenic spots of province||Times (days)||traffic fee (yuan)||Host fee (yuan)|
|1||All spots in Henan||14||2656||2000|
|All spots in Hubei (exclude Enshi Tujia and Miao Autonomous Prefecture, Enshi Grand Canyon Scenic Area)||15||2686||2350|
|2||All spots in Shanxi, Beijing, Xi'an Yanan Huangling Mausoleum Scenic Area||15||3476.9||2150|
|All spots in Tianjing, Hebei||15||3616.2||2650|
|3||All spots in Hunan, Enshi Tujia and Miao Autonomous Prefecture, Enshi Grand Canyon Scenic Area in Hubei||15||3517.7||2450|
|Spots in Shaoguan, Qingyuan, Guangzhou, Foshan of Guangdong||14||3888.5||2050|
|4||Spots in Shenzhen, Huizhou, Meizhou of Guangdong Spots in Longyan, Xiamen, Quanzhou of Fujian||14||4516.8||1950|
|All spots in Guangxi||11||3814||1400|
|5||All spots in Hainandao||13||5290||2150|
|All spots in Shandong||13||3607.8||200|
|6||All spots in Liaoning, Jinling, Mudanjiang of Heilongjiang||15||6414||6900|
|Spots in Heilongjiang (exclude Mudianjiang)||15||7465||4950|
|7||Spots in Jiangsu (exclude Zhenjing, Yangzhou, Taizhou, Huaian), All spots in Shanghai and Xi'an Qin Shihuang Terracotta Army Museum and Huaqing Hot Spring scenic spot||15||3211||6900|
|All spots in Anhui, Huzhou and Jiaxing of Zhejiang||15||3944||6900|
|8||Spots in Zhejiang (exclude Huzhou and Jiaxing)、Jiangwan scenic area in Wuyuan of Jiangxi and Jingdezhen City area, Famen Temple Buddha culture in Baoji of Shanxi County||15||4297||6900|
|Spots in Jiangxi (exclude Jiangwan scenic area in Wuyuan of Jiangxi and Jingdezhen City area), Fujian (exclude Longyan, Xiamen, Quanzhou)||15||4317||7350|
|9||Kanas, Turpan, Tianshan Tianchi spots in Xinjiang, The big wild goose pagoda in Shanxi||14||7479||1500|
|Nalati scenic area, scenic area of the old city of Kashi golden Populus in Xinjiang||15||8755||1750|
|10||Tianshan Grand Canyon, Koktokay, Bosten Lake Scenic Area in Xinjiang, Dunhuang Crescent Spring, Jiayuguan cultural relics in Gansu||14||7108||1500|
|All spots in Sichuan||15||2907||2350|
|11||All spots in Xizang, Qinhai, Maiji Mountain in Gansu||13||13150||1650|
|All spots in Ningxia||12||2299||2150|
|Dazu area, Wushan small Three Gorges spots in Chongqing||5||1955||600|
|12||All spots in Yunnan||14||5626||1800|
|All sopts in Guiyang, Chongqing (exclude Dazu area, Wushan small Three Gorges spots)||14||2976||2450|
|13||Sopts in Huaian, Yangzhou, Zhenjiang, Taizhou||9||2616.4||1450|
|Total||12 years 9 days||121589.3||76450|
The self driving tour to finished the national 5A level scenic spots spend on 12 years and 9 days. In the planning process, the the spots in same areas visit toghter, but taking into account each year only 30 days time to visit, so in a year we will arrange the tour attractions in different regions to improve the utilization rate of the time, on the other hand can also reflect differences in different areas of the landscape, fully enjoy the great rivers and mountains of the motherland and enhance the overall quality of tour, such as in the fifth year of visit Shandong and Hainan, the ten year visit Xinjiang and Sichuan, the eleventh year of visit Tibet, Qinghai, Gansu, Ningxia and other northwest regions and Chongqing.
We divided the country into seven regions, according to the defined conditions and requirements eatablish a linear programming model. Then we plan out every time travel route under the background of "Chinese postman problem", according to the specific conditions, uphold the principle of concentrated spots together travel and scatter spots combination travel to improve the tour quality, reduce travel time and travel times.
The design integrates the constraints of the linear programming, Chinese postman problem, variable neighborhood search algorithm etc. eatablish a mathematical model, get the reasonable results under many conditions. Due to our limited level, and collected information on the existence of errors, this result is not the best solution, but it has been possible to make full use of condition, balance the time and cost, to ensure the quality of travel.