| The subject of this paper derives from the actual Airport Pickup and Delivery Service(APDS) in a city. The optimal allocation and scheduling of vehicles are the kernel of the research, the chief content of which is the optimization of the traffic activities in this service,such as the routes and departure time of vehicles. The purpose of the research is to complete the pickup and delivery of customers with the lowest cost subject to all of the requirements put forward by customers and Flight-Ticket-Sale-Agents. Integer programming model used to establish an abstract problem, based on which the appropriate combinatorial optimization algorithm is then selected or designed to solve the problem.From the point to solve the practical problems in APDS, the following three problems need to be studied. First of all, in most research, the vehicle routing prolems are generally treated via the representation of the road network as a weighted complete graph. Each arc of the graph represents the shortest route for a possible origin-destination connection, but the shortest route modeled by this arc is computed according to only the distance criterion. And assuming a uniform speed for all vehicles, such representation suggests that travel time of a path can correspond with its length. However, uniform constant vehicle speed does not meet the actual traffic situation, it may fail to meet the time demands in APDS to ignore the issue while modeling. Secondly, it is the basis of route optimization that modeling an abstract representation of real urban traffic network. And comes the problem called bicriterion shorest problem(BSP) that how to find all the Pareto paths when each link is asigned both length and travel time. The problem often occurs as a subproblem in transportation models and combinatorial optimization. Thirdly, the direct research results of APDS are mainly the optimization problem and its algorithm that are usually too complex and difficult to apply to reality. In order to use the high-performance computing, it is necessary to model the optimization model and its algorithm with a language that comoputers can identify and also to design a dedicated software system.Four major researches have been completed for solving the above three problems. For the first problem, a multigraph representation with Pareto arcs of the road network for generally vehicle routing problems in APDS is proposed and then a so-called fixed sequence arc selection problem is applied to build a integer programming mathematical model. A dynamic programming solution method is given for the problem. For the second problem, the BSP in the fixed sequence arc selection problem is described with representation of real urban traffic network and a branch-bound enumeration is proposed to work out all the Pareto paths. In the study of the third problem, there are two works. A method is pointed out to model the optimization problem and its algorithm with Object-Oriented computer language. Related discussions are given to realize the organization and management of them. Also, the application of Unified Process Modeling theory is given for two specific needs of the city APDS should follow when designing a computer system. |
PDF Full Text Request