American Journal of Applied Mathematics
Volume 4, Issue 4, August 2016, Pages: 192-196

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

Email address:

(Yawei Li)
(Yandong Li)
(Xiaorong Li)

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:

7+;

(1) If M=4, and

Visitor Can end the play of this scenic spot.

If

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

If

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

Figure 1. 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:

Table 1. The annual tourist attractions confluence.

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.

4. Conclusion

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.


References

  1. Jun Zhang. Model and Algorithm for the Multi DePot Vehiele Routing Problem with Time Windows [D]. dalian: Dalian University of Technology, 2010.
  2. Peng Hui. Introduction of psychological variables in travel choice behave or model of medium and remote passengers [J]. Journal of Chang'an University, 306-312.
  3. Hong Lianxi. Multi-phase iterative heuristic approach for solving MDVRPTW [J]. Computer Engineering and Applications, 2007, 43 (26): 217-222.
  4. Mladenovic N, Hansen P. Variable neighborhood search [J]. Computers and Operations Research. 1997, 24 (11): 1097-1100.
  5. Wang Renming. Improved variable neighourhood search algorithm for VDRP [J]. Computer Engineering and Applications, 2014, 50 (2): 237-241.
  6. Li Ning. Particle Swarm Optim ization for Vehicle Routing Problem with Time windows [J]. Systems Engineering-Theory & Practice, 2004 (4): 130-135.
  7. Section. Dynamic Vehicle Routing Using an Improved Variable Neighborhood Search Algorithm [J]. <<Journal of Applied Mathematics>>, 2013, 2013 (1): 1-21.
  8. DC Paraskevopoulos, PP Repoussis, CD Tarantilis, G Ioannou, GP Prastacos. A reactive variable neighborhood tabu search for the heterogeneous fleet vehicle routing problem with time windows [J]. <<Journal of Heuristics>>, 2008, 14 (5): 425-455.
  9. A Stenger, M Schneider, D Goeke. The prize-collecting vehicle routing problem with single and multiple depots and non-linear cost [J]. <<Publications of Darmstadt Technical University>>, 2013, 2 (1-2): 57-87.
  10. PP Xiong, YG Dang, T Yao, J Cui. The Research on the Modeling Method of Background Value Optimization in Grey Verhulst Model [J]. <<Chinese Journal of Management Science>>, 2012.
  11. LI Fu-Chang, Y Wang, ZF Zhang. Transportation and Inventory Outsourcing Decision-makings of Fourth Party Logistics Based on Third Party Logistics Competition [J]. <<Chinese Journal of Management Science>>, 2010, 18 (6): 71-81.

Article Tools
  Abstract
  PDF(361K)
Follow on us
ADDRESS
Science Publishing Group
548 FASHION AVENUE
NEW YORK, NY 10018
U.S.A.
Tel: (001)347-688-8931