2012年美賽論文B題.doc

Team #12911 Page 22 of 21Camping 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 teams 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 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 obtained 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 managers, 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 sensitivity 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 with each other, and together indicate the feasibility and reliability of our solution to some extent.Keywords: PSO, discrete dynamic programming, topology, campsiteCONTENT1PROBLEM STATEMENT22PROBLEM ANALYSIS22.1Background and Approaches22.2Our Own Understanding22.3Outline of Our Analysis33ASSUMPTIONS AND NOTATIONS43.1Assumptions43.2Notations and symbols54MODELING AND SOLUTIONS64.1Modeling64.1.1Simplifying conditionsPreliminary SimplificationMatrix Expression64.1.2Establish modelingUnderstanding of Influencing FactorsConstraint Conditions and Objective Functions84.2Solutions114.2.1Introduction of PSO Algorithm114.2.2The Procedure of Revised PSO134.2.3Optimal Schedule164.2.4The Relation between the Operation Schedule and Y185CONCLUSIONS205.1Strengths205.2Weaknesses205.3Improvements206REFERENCES211 Problem StatementInthispaper,wetrytosolvetheproblemofschedulingrivertourismtoutilizethecampsitesinthebestwaypossible.VisitorstotheBigLongRiver(225miles)canenjoyscenicviewsandexcitingwhitewaterrapids.Theonlywaytoenjoyitistotakearivertripthatrequiresseveraldaysofcamping.Passengerstakeeitheroar-poweredrubberrafts,whichtravelonaverage4mphormotorizedboats,whichtravelonaverage8mph.Thetripsrangefrom6to18nightsofcampingontheriver.Themanagerofthisriverwantseverytriptoenjoyawildernessexperience,withminimalcontactwithothergroupsofboatsontheriver.Currently,XtripstravelontheBigLongRiverduringasixmonthperiodeveryyear.ThereareYcampsitesontheBigLongRiver,distributedfairlyuniformlythroughouttherivercampsitesandnotwosetsofcamperscanoccupythesamesiteatthesametime.Problem:HowmanymoreboattripscouldbeaddedtotheBigLongRiversriverseasoninordertoutilizethecampsitesinthebestwaypossible? 2 Problem Analysis2.1 Background and ApproachesThis problem has a close contact 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 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 operation 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 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 meet 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 not 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 expression 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 boats 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 occupy, 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 information 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 use 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 day 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 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 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 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 traveling 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 of 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.the 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個月內(nèi)4 Modeling and Solutions4.1 Modeling4.1.1 Simplifying conditions Preliminary SimplificationDuring the whole journey, every 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 process.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 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 as possible. Thus we can see this condition as the constraints of the optimizing problem. 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 represents 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 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 no 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, 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 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 modeling 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 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 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 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 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 season begins. Thus we could make the river traffic more efficient and rational. 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 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 and 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 suppose the date of every team is and it must satisfy: (4)We also need to obtain how many nights the trip stays and where it locates. And we expect a table like below:Tab. 3 Example of Final Conclusion of Our ExpectationAll the equations above meet: (5)To simplify and calculate the variables above, we need to adopt a total of a quite number of variables. The number of variables is: (6)Apparently, even if the operating scale is not large, we still have thousands of variables to deal with. Therefore we will try to decrease it based on our reasonable assumptions。We suppose that the every boat sails the same time every day in their trips, which means they sails the same miles per day. And we assume that every boat sails at from 8 am to 18 am.Apparently the least time of everyday sailing is , here (mph).Thus we have: (7)The miles that each team moves forward every day： (8)And we get: (9)and, (10)Also the number of campsites that the team passes by but does not stay is： (11)First FinalCampsiteFig.1 Simulation of Travel ProcessThe number of campsites between every two neighboring teams according to Fig.1: (12)And (13) How is the objective function of optimization model determined? As we know, since managers always wish more tourists to join in the travel, the most direct objective function is the total trip number X which is also the variable that is to be figured out.Thus, we define the utilization percentage of campsite: (14)Obviously, the more teams are involved in travel in a finite time period, the higher utilization percentage is attained. Therefore, we can define another objective function: (15)We also have： (16)Thus, we define the final objective function: (17)As we state above, the boats behind could never transcend the boats in front. So we get the constraint conditions: (18)Finally we yield the optimizing model:(19)In addition, because 6-month-long time span brings about large verbose calculation, we need to decrease the time span and divide the whole complex problem into a few easier questions to deal with. However, simply splitting the topic will result in the tremendous errors of optimal results 5.As we know, one month is a common period for people to record events. We assume that it is also convenient for managers to make the schedule, and we use one month as the period to discuss. By solving problems in the smaller period, we simplify th