2012年美赛论文B题.doc

Camping along the Big Long River Abstract In 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 campsite CONTENT 1PROBLEM STATEMENT2 2PROBLEM ANALYSIS2 2 1Background and Approaches2 2 2Our Own Understanding2 2 3Outline of Our Analysis3 3ASSUMPTIONS AND NOTATIONS4 3 1Assumptions4 3 2Notations and symbols5 4MODELING AND SOLUTIONS6 4 1Modeling6 4 1 1 Simplifying conditions6 4 1 1 1Preliminary Simplification6 4 1 1 2Matrix Expression6 4 1 2 Establish modeling7 4 1 2 1Understanding of Influencing Factors7 4 1 2 2Constraint Conditions and Objective Functions8 4 2Solutions11 4 2 1 Introduction of PSO Algorithm11 4 2 2 The Procedure of Revised PSO13 4 2 3 Optimal Schedule16 4 2 4 The Relation between the Operation Schedule and Y18 5CONCLUSIONS20 5 1Strengths20 5 2Weaknesses20 5 3Improvements20 6REFERENCES21 1 Problem Statement In this paper we try to solve the problem of scheduling river tourism to utilize the campsites in the best way possible Visitors to the Big Long River 225 miles can en joy scenic views and exciting white water rapids The only way to enjoy it is to take a river trip that requires several days of camping Passengers take either oar powered rubber rafts which travel on average 4 mph or motorized boats which travel on average 8 mph The trips range from 6 to 18 nights of camping on the river The m anager of this river wants every trip to enjoy a wilderness experience with minimal c ontact with other groups of boats on the river Currently X trips travel on the Big Lon g River during a six month period every year There are Y camp sites on the Big Long River distributed fairly uniformly throughout the river campsites and no two sets of c ampers can occupy the same site at the same time Problem How many more boat trips could be added to the Big Long River s river sea son in order to utilize the campsites in the best way possible 2 Problem Analysis 2 1 Background and Approaches This problem has a close contact with people s 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 Understanding Similar 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 Analysis Synthesizing 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 Notations 3 1 Assumptions Assuming 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 symbols Tab 1 Notations and symbols NotationMeaning i Nthe camp duration of one trip whose trip number is i i vthe speed of one raft or boat whose number is i i j L the sequence number of campsite where No trip stays at momentij i ttravelling time of No every day i i Stravelling miles of No every day i i nthe total of campsites which Team No passes by but does not stay i i Tthe date that Team No starts i k utilization percentage of the campsite No k Ythe total number of campsites Xthe maximal total number of trips Xthe average number of boats started per day i Athe frequency of No campsite occupied within 6 months i 号营地的频率占用 6 个月内 4 Modeling and Solutions 4 1Modeling 4 1 1Simplifying conditions 4 1 1 1 Preliminary Simplification During 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 4 1 1 2 Matrix Expression Based 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 Campsite 000 010 000 000 010 000 001 000 100 000 The 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 2Establish modeling 4 1 2 1 Understanding of Influencing Factors From the manager s 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 4 1 2 2 Constraint Conditions and Objective Functions We 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 18Y For X teams we determine every team will stay nights which means they i N will arrive at a total of campsites during their trips must obey i N i N 2 618 i N The velocity of every boat is i v 3 4 8 i vmph 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 i T 4 0180 i Tdays 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 Expectation 1 1 L 1 2 L 1 1 N L 2 1 L 2 2 L 2 2 N L 1X L 2X L X X N L All the equations above meet 5 1 1 i iXjN 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 number of variables xXii NvXNT 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 i t 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 225 1 i Yv 8 i v mph Thus we have 7 225 10 1 i i t Yv The miles that each team moves forward every day 8 iii Svt And we get 1 225 225 1 1 i i i L Y S N 9 and 1 225 1 jj ii Ni N SLL Y 10 Also the number of campsites that the team passes by but does not stay is 11 1 1 225 i i SY n Fig 1 Simulation of Travel Process The number of campsites between every two neighboring teams according to Fig 1 12 1 11111 1 225 iiiiiiii Y MTTtvTTtv And 13 1 1 1iii jij MLL 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 180 i i A 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 max i i f We also have 16 180180 ii i iii AN Thus we define the final objective function 17 1 2 i i fNiX As we state above the boats behind could never transcend the boats in front So First Final Campsite we get the constraint conditions 18 11 iiii nMn Finally we yield the optimizing model 19 1 1 1 11111 1 1 1 1 618 48 0180 225 10 1 225 225 1 1 1 225 1 1 225 1 225 i i i i i i iii i i i ii ji j i i iiiiiiii iii jij i MaximumN subjecttoN vor T t Yv Svt L Y S N Y SLL SY n Y MTTtvTTtv MLL n 1 1 2 1 2 iii i Mn iX jN YX 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 the amount of calculation 4 2 Solutions 4 2 1Introduction of PSO Algorithm PSO algorithm is one of the common swarm intelligence methods to solve problems about parameter optimization parameter design and combinatorial optimization It has been achieved by programs and has impressive optimization efficiency because of the combination of swarm intelligence and learning function As a result PSO is widely used in science and technology researches The core idea of PSO is derived from the process of simulating social behavior As a stylized representation of the movement of organisms in a bird flock or fish school it is a metaheuristic as it makes few or no assumptions about the problem being optimized and can search very large spaces of ca