| Περιγραφή: |
In recent years, there has been considerable progress in the area of logistics. The main forces behind this evolution are computer based technologies such as geographic information systems (GIS), global positioning systems (GPS) and intelligent highway information systems. All these technologies facilitate better decisions on routing, assignment, distribution as well as many other logistics-related problems. Most of the research in the last twenty years was focused on the optimization of networks either static or deterministic. A network can be defined as static when all its parameters are known a priori, it does not change over time, and is deterministic when all parameters are deterministically known. Models that anticipate real-time information and can account for parameter uncertainty are called either dynamic or stochastic. These types of models are receiving increasingly more interest from many researches in the area. This is the case because these models allow for more accurate representation of reality, by continually updating their data with new input from the real world. These models are certainly more difficult to solve. However, given the evolution of information technology, we could safely claim that they are the best choice for logistics problem solving. Researchers tackle these problems, by constructing algorithms, which are typically problem specific and extensions of the corresponding static algorithms. The traditional design and analysis of static algorithms assumes that an algorithm has complete knowledge of the entire input. However, this assumption is often unrealistic in practical applications. Many of the practical algorithmic applications, however, are online by nature. For these applications the input is only partially available because some data becomes available in the course of operation. Often, this information is unavailable at the time routing decision must be made. An online algorithm must generate output without knowledge of the entire input.
The problem of concern in this dissertation is the well known “Dial-a-Ride” or “Pickup and Delivery” Problem and its variation called “Online Dial-a-Ride”. This problem can be considered as a special case of the general “Vehicle Routing Problem”. The “Dial-a-Ride Problem” is an important and difficult problem encountered in several contexts. It is becoming increasingly important as the pressure for optimal utilization of the available capacity of an existing fleet of vehicles intensifies, due to energy and environmental impact concerns. An extension to the traditional “Dial-a-Ride problem” (DARP) is the “Online Dial-a-Ride problem” which deals with the continuous flow of trip demands during course of operation. What is required is to construct online algorithms, capable of adapting to the continuous stream of incoming information. We can imagine the “Online Dial-a-Ride problem” as a “Dial-a-Ride problem” that has to be solved by an online algorithm each time a new trip demand occurs dynamically. We will examine this problem in more detail later in this document. For this dissertation, six different dial-a-ride algorithms have been implemented. The first four are static dial-a-ride algorithms while the remaining two can be considered as pure online algorithms. Finally, a methodology concerning the profitability of a proposed Demand Responsive Transportation System has been developed, as well as the underlying algorithm. |
