2012年美赛论文B题.doc

《2012年美赛论文B题.doc》由会员分享，可在线阅读，更多相关《2012年美赛论文B题.doc（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、东方文化培训中心经营方案Camping along the Big Long RiverAbstractIn this paper, we try to solve the problem of scheduling river tourism which contains different tour durations and various speeds of propulsion. We propose a plan to utilize the camping sites as much as possible, and guarantee that two different te

2、ams do not meet during all their trips, in order to provide tourists with the wildness experience.In model construction, under a series of necessary assumptions including trip duration and campsite states, we make the discrete dynamic programming on the Big Long River operation using the constraints

3、 and objective functions. Moreover, a matrix form is introduced to describe the states of campsites succinctly and comprehensibly. We improve particle swarm optimization (PSO) to Integer-PSO algorithm which can solve the large-scale integer optimization problems. Then the optimum solution is obtaine

4、d under our assumptions.Through careful calculation, we have proved that this optimum solution satisfies the basic requirement of the topic. When there are 20 campsites, we figure out that the optimal solution is 43 trips. With the further discussion about the different demands of tourists and manag

5、ers, we improve the current model and take more factors into account such as utilization percentage and different campsite quantity. We make the schedule of teams and find the law of schedule topology structure which helps us certify our model and suggest a better theory.We test the robustness and s

6、ensitivity of the models by accurate simulation above and obtain some theoretical conclusions of the arrangement for river tourism. The obtained optimal solution performs promisingly when considering different conditions. Therefore, the theoretical guarantee and the simulation result are consistent

7、with each other, and together indicate the feasibility and reliability of our solution to some extent.Keywords: PSO, discrete dynamic programming, topology, campsite页脚内容25CONTENT1PROBLEM STATEMENT22PROBLEM ANALYSIS22.1Background and Approaches22.2Our Own Understanding22.3Outline of Our Analysis33ASS

8、UMPTIONS AND NOTATIONS43.1Assumptions43.2Notations and symbols54MODELING AND SOLUTIONS64.1Modeling64.1.1Simplifying conditions64.1.1.1Preliminary Simplification64.1.1.2Matrix Expression64.1.2Establish modeling74.1.2.1Understanding of Influencing Factors74.1.2.2Constraint Conditions and Objective Fun

9、ctions84.2Solutions124.2.1Introduction of PSO Algorithm124.2.2The Procedure of Revised PSO144.2.3Optimal Schedule164.2.4The Relation between the Operation Schedule and Y185CONCLUSIONS205.1Strengths205.2Weaknesses205.3Improvements206REFERENCES211 Problem StatementInthispaper,wetrytosolvetheproblemofs

10、chedulingrivertourismtoutilizethecampsitesinthebestwaypossible.VisitorstotheBigLongRiver(225miles)canenjoyscenicviewsandexcitingwhitewaterrapids.Theonlywaytoenjoyitistotakearivertripthatrequiresseveraldaysofcamping.Passengerstakeeitheroar-poweredrubberrafts,whichtravelonaverage4mphormotorizedboats,w

11、hichtravelonaverage8mph.Thetripsrangefrom6to18nightsofcampingontheriver.Themanagerofthisriverwantseverytriptoenjoyawildernessexperience,withminimalcontactwithothergroupsofboatsontheriver.Currently,XtripstravelontheBigLongRiverduringasixmonthperiodeveryyear.ThereareYcampsitesontheBigLongRiver,distrib

12、utedfairlyuniformlythroughouttherivercampsitesandnotwosetsofcamperscanoccupythesamesiteatthesametime.Problem:HowmanymoreboattripscouldbeaddedtotheBigLongRiversriverseasoninordertoutilizethecampsitesinthebestwaypossible? 2 Problem Analysis2.1 Background and ApproachesThis problem has a close contact

13、with peoples life and production. The background of this problem is how to plan the travelling routes for the managers of the river to make higher profits, and the answer of the problem can be applied to the field of city planning, public transportation and production logistics.However, low and over

14、 exploitation of travel resources are common drawbacks in the field of river tourism, partly because of the lack of theoretical foundations in scientific calculation. Therefore, the discussion and solution of this problem is of great importance for society.2.2 Our Own UnderstandingSimilar to the ope

15、ration of trains, the tourists choose their specific travel plan from many predetermined schedules made by managers of the river. That is to say, managers could pick up the specific tourists according to their choices of different types of boats and duration. Therefore we cannot adopt queuing model

16、to solve the problem.Our goal is to help the managers to obtain the highest profits, in other words, the highest number of the trips. At the same time, we are required to respect the tourists to give them the maximum wild experience, which means we try to avoid the situation that two or more teams m

17、eet with each other in the tour.We take these two factors as objective functions, and try to get constraint conditions from the real practical situation of this problem. In this way, we use optimization method to get the optimal solution of this problem.However for reasons of convenience, if we do n

18、ot make some necessary limits and assumptions of the problem, we will have a fairly tough job on data processing and it is not easy for us to get the available results. Therefore, in our solution part, we have to make reasonable constraints and limits so as to get the complete and feasible expressio

19、n in mathematics. For example, we presume that there is no transcendence between boats, showing that two different teams could not meet during their trips. Also, for the sake of simplicity of mathematics, we suppose that the boats are always at the constant speed once starting 1.The two types of boa

20、ts can be represented by two parameters in mathematics, and at a certain night there are two states for every campsite: with or without team staying. In mathematics, we can represent them with 1 and 0. According to the requirement of the problem, every campsite has at most one traveling team to occu

21、py, so we just try to assure the value of campsite state is no more than 1 within one night. And to satisfy the requirement of no encounter between teams, we need to guarantee that the course of the boat in front is always larger than the boat behind.2.3 Outline of Our AnalysisSynthesizing the infor

22、mation that we have, we get to know that the way for tourists to select the duration and the type of the boats needs to be considered by managers when they are making plan. Also the manager needs to ensure that the location of the boat in front can make an effect on the boat behind. To fully make us

23、e of the campsites in order to accommodate more tourists, the travel agency needs to work out a well-calculated plan about the number of tours that have different duration and their corresponding trip start dates. We also notice that it is not likely that every campsite has a team to occupy every da

24、y 2.By means of this series of processing, we establish and optimize our mathematical model. And finally we get the optimal result of X. In addition, aiming at the distinct goals of the tourists and manager, we can make further optimization by constructing another destination function.3 Assumptions

25、and Notations3.1 AssumptionsAssuming that the six months mentioned in the problem equals to continuous 180 days.One or a few teams can start their trips in a day and they must start together.Every team travels the same miles per day. But different team can travel different miles in a day.Every team

26、strictly conforms to the predetermined plan made by the manager.The interval of every two neighboring campsites remains strictly uniform.We consider both oar-powered rubber rafts and motorized boats sails on a constant speed, including the accelerating part at the beginning and the decelerating when

27、 finishes.The flow speed of the river maintains steady, and the weather situation does not affect the speed of the boats.Every boat can only stay one night at the same campsite.The boats behind could never transcend the boats in front.Every team can only choose one kind of boat, which means the trav

28、eling speed of the boat of every team does not change during the course.The team cannot return to the campsites behind; they could only move forward along the tour route.3.2 Notations and symbolsTab. 1 Notations and symbolsNotationMeaningthe camp duration of one trip whose trip number is the speed o

29、f one raft or boat whose number is the sequence number of campsite where No. trip stays at momenttravelling time of No. every daytravelling miles of No. every daythe total of campsites which Team No. passes by but does not staythe date that Team No. startsutilization percentage of the campsite No.th

30、e total number of campsitesthe maximal total number of tripsthe average number of boats started per day the frequency of No. campsite occupied within 6 months号营地的频率占用6个月内4 Modeling and Solutions4.1 Modeling4.1.1 Simplifying conditions4.1.1.1 Preliminary SimplificationDuring the whole journey, every

31、team could stay at only one campsite per night and could not be transcended by other teams. Through simple calculations, we know that any boat will finish their travel if they sail ten hours a day within six days. Obviously, the teams are not all at their full speed moving forward in the travel proc

32、ess.After further analysis, we decide to define the index of the progress of the travel in terms of the location of the campsites. That is to say, one boat cannot transcend another boat which is closer to the termination. According to the problem, 18 days-long tour is allowed, apparently the number

33、of the campsites Y is no less than 18. If not, the river will not be able to supply sufficient campsites to accommodate 3. And since not all the all the types of the tour is 18 days long, there exist the campsite that has no team staying. In addition, we are supposed to make use of campsites as much

34、 as possible. Thus we can see this condition as the constraints of the optimizing problem.4.1.1.2 Matrix ExpressionBased on these considerations above, we utilize the matrix to denote the state of the specific campsite at the specific night. There are only two elements in the matrix: 0 and 1. 0 repr

35、esents that the boat does not stay at this campsite at the night; 1 indicates that the boat stays at the campsite this night. In this way, at the certain time, all the boats in their trips can be represented by the matrix with X rows and Y columns. And the duration time of the trip can be indicated

36、by the number of change of the matrix from the beginning to the end of their trips.For example, one certain campsite at the certain night could be presented by the following table:Tab. 2 Example of State of Campsite000010000000010000001000100000The most original matrix is the zero-matrix, denoting n

37、o team starts their travel. After the original quiet state, every row of the matrix begins to have element 1 and continuously moving towards the right row. until the elements of the row become all-zero, which means the boat has finish the travel and arrive at the termination. Adding all the matrixes

38、, we get the sum of the row elements of the matrix and the value is between 6 and 18. In this way we get all the campsites and boats states during all the travel period.Meanwhile, the 6-month-long duration calls for very large amount of computation, and brings difficulty in feasibility to apply this

39、 method. For the sake of simplifying the problem, we might divide the 180 days into 10 periods, with 18 days per period. In the later discussion, we could exert our model in a relatively small period, so as to reduce the verbose amount of computation and make our solutions available.4.1.2 Establish

40、modeling4.1.2.1 Understanding of Influencing FactorsFrom the managers point of view of making profits, the possible largest number of trip teams is preferred. We are required to help manager to give the optimal river trips utilization plan.According to the description of the problem, there are a lot

41、 of constraints to limit the motivation of teams. What we should do is to exert the maximum utilization percentage of the campsites in the finite time. The travel plan of the boats behind is partly affected by the team in front. For example, the Team 2 should avoid meet and stay at the same campsite

42、 at the same time as the Team 1. Similarly, for the Team 3, 4 and more, their running states, involving the running speed and traveling time, are partly influenced by the boats in front 4.From this, we realize we could use the time series model to solve the problem. The plan of the boats in front is

43、 relevant to the ones behind, and the influence could be accumulated little by little, resulting in the large fluctuation of the whole plan of managing the river. Without the carefully calculation, the administrator of the river will lose quite a lot profits.Therefore, we need to optimize the method

44、 of increasing the number of the team, on the basis of the previous one. For the purpose of this, we might as well lay more emphasis on directly planning the number of the team. In other words, we need to consider the operating scheme of every boat in the six month long travel season, before the sea

45、son begins. Thus we could make the river traffic more efficient and rational.4.1.2.2 Constraint Conditions and Objective FunctionsWe know that the travel duration of every boat is limited in 6 to 18 nights and we assume that no team is allowed to stay in the same campsites more than 1 night. So the

46、number of campsites Y must satisfy： (1)For X teams, we determine every team will stay nights, which means they will arrive at a total of campsites during their trips must obey: (2)The velocity of every boat is: (3)To get the optimal travel plan, we need to make further instructions and improvement a

47、nd introduce more variables to represent the possible practical problems in operation. For the river manager, the duration and start date plan of every team is extremely important. So it is necessary for us to provide the specific duration and date. To simplifying the problem, we assume that one or a few teams can start their trips in a day and they must start at the same time, for example 8:00 a.m. We sup