Vehicles that today are searching for a place to stop impacts other vehicles in cities. It can also be seen that the number of vehicles that desire to conduct a pick-up or drop-off increases with an increased number of ride-hailing services. New technology routing advises for such vehicles could improve the overall performance of a traffic network. This thesis analyses therefore how a routing strategy, that incorporates curbside availability information, can impact the performance. To analyse the effects of how curbside availability information can impact a network, a microscopic traffic simulation model was constructed in PTV Vissim and two different routing strategies were developed and implemented in the model. One strategy that represents the scenario of today where vehicles searches the traffic network while attempting to make a stop at a pick-up and drop-off slot. The second strategy routes vehicles to a slot based on curbside availability information. This strategy directs vehicles to an available slot and therefore reduces the time a vehicle is cruising before a stop has been made. A simulation experiment was set-up to compare the strategies that were developed with different penetration rates of vehicles that desired to stop. The results shows that the average travel time can be reduced with up to 25.2\% when vehicles have information compared to the scenario with no information. Similar findings is identified for average delay per vehicle which is reduced with up to 49.0\% and average traveled distance decreased with up to 15.5\%. The results of this thesis needs however to be studied in a wider context in order to draw reliable conclusions. The thesis propose further investigations whether a strategy that incorporates availability information can be implemented in a real world scenario and further investigations whether an implementation of a strategy like this would be socioeconomic beneficial.

京都大学 / 0048 / 新制・課程博士 / 博士(工学) / 甲第19290号 / 工博第4087号 / 新制||工||1630(附属図書館) / 32292 / 京都大学大学院工学研究科都市社会工学専攻 / (主査)教授 谷口 栄一, 准教授 宇野 伸宏, 准教授 QURESHI,Ali Gul / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DFAM

Since Hurricane Katrina, extensive studies have been conducted aiming to optimize the transit vehicle routing in the event of an emergency evacuation. However, the vast majority of the studies focus on solving the deterministic vehicle routing problem that all the evacuation data are known in advance. These studies are generally not practical in dealing with real-world problems which involve considerable uncertainty in the evacuation data set. In this dissertation, a SmartEvac system is developed for dynamic vehicle routing optimization in emergency evacuation. The SmartEvac system is capable of processing dynamic evacuation data in real time, such as random pickup requests, travel time change, network interruptions. The objective is to minimize the total travel time for all transit vehicles. A column generation based online optimization model is integrated into the SmartEvac system. The optimization model is based on the following structure: a master problem model and a sub-problem model. The master problem model is used for routes selection from a restricted routes set while the sub-problem model is developed to progressively add new routes into the restricted routes set. The sub-problem is formulated as a shortest path problem with capacity constraint and is solved using a cycle elimination algorithm. When the evacuation data are updated, the SmartEvac system will reformulate the optimization model and generate a new routes set based on the existing routes set. The computational results on benchmark problems are compared to other studies in the literature. The SmartEvac system outperforms other approaches on most of the benchmark problems in terms of computation time and solution quality. CORSIM simulation is used as a test bed for the SmartEvac system. CORSIM Run-Time-Extension is developed for communications between the simulation and the SmartEvac system. A case study of the Hurricane Gustav emergency evacuation is conducted. Different scenarios corresponding to different situations that presented in the Hurricane Gustav emergency evacuation are proposed to evaluate the performance of the SmartEvac system in response to real-time data. The average processing time is 28.9 seconds and the maximum processing time is 171 seconds, which demonstrate the SmartEvac system’s capability of real-time vehicle routing optimization.

[pt] Com o advento do comércio eletrônico, o mercado passou a atuar cada vez mais intensamente através de suas fronteiras geográficas e, como consequência, as empresas necessitam constantemente de inovações e melhorias na gestão de suas operações para se manterem competitivas. Desta forma, encontrar soluções de fretes que consigam atender longas distâncias em um curto prazo pode ser tão decisivo quanto o fator custo, por isso, os estudos acadêmicos em otimização de rotas intermodais estão em contínua evolução para se aproximarem dos modelos reais. Nesse contexto, esta dissertação busca solucionar um problema de roteamento aeroterrestre de transporte de cargas, com linhas aéreas predeterminadas e frotas próprias e heterogêneas. Uma extensão do problema de roteamento de veículos é elaborada com a inclusão de arcos que representam as possíveis linhas aéreas. O modelo é aplicado em um resolvedor de Programação Linear Inteira Mista e, primeiramente, é realizado um teste de validação com demandas fictícias em todos os locais. Em seguida, o modelo é aplicado no planejamento real de um órgão governamental em três períodos distintos. São realizadas análises sobre a velocidade de solução; a decisão de utilizar o modal aéreo, terrestre ou intermodal; e sobre os ganhos do modelo. Em comparação com as rotas efetivamente realizadas, o modelo traz redução de 7 por cento a 55 por cento dos custos com transportes. Com esses resultados, conclui-se que é imprescindível que os detentores de frota própria de aeronaves e caminhões utilizem o modal aéreo apenas como atividades acessórias, ou seja, que estejam cumprindo outras missões em conjunto (transporte de passageiros, por exemplo), ou para atender locais remotos. / [en] With the advent of e-commerce, the market has started to act more and more intensively across its geographic borders and, as a consequence, companies constantly need innovations and improvements in the management of their operations in order to remain competitive. Thus, finding freight solutions that can serve long distances in the short term can be as decisive as the cost factor, for this reason, academic studies in intermodal routing optimization are continually evolving to approach real models. In this context, this thesis seeks to solve a problem of air-land cargo routing, with predetermined airlines and their own heterogeneous fleets. We elaborated an extension of the vehicle routing problem by including arcs that represent overhead lines. The model is applied to a Mixed Integer Linear Programming solver and, firstly, a validation test is performed with fictitious demands in all locations. It is then applied to the actual planning of a government agency in three different periods. We performed analyses on the solution speed; the decision to use the air, land or intermodal modal; and about the earnings of the model. In comparison with the routes actually carried out, the model reduces transport costs by 7 percent to 55 percent. With this results, it is concluded that it is essential that owners of their aircraft and trucks fleet use the air modal only as secondary activities, in other words, that they are fulfilling more missions together (transportation of passengers, for example), or to deliver to remote locations.

As the older population grows larger there is a growing need to provide health care at home. This services are generally done without operational research. As more people will require home care there will be a need to increase the efficiency of the service while keeping the quality high. The purpose of this thesis is to investigate how we can use operation research in home care as well as define how we can model the quality and use those quality parameters in order to offer the best possible service. The model uses VRP with Time windows in order to schedule the routes and incorporates service requirements at the customers. A solution is obtained by first constructing an initial solution that fulfills the duration constraint. Then it uses a local search with a dynamic insertion heuristic to improve on the solution. Tabu search is used as a meta-heuristic to prevent the solution the get stuck in a local minima. The solver is used in order to optimize the quality parameters. The result obtained can be used to help home care providers to determine the level of quality they can supply with a limited budget / När den äldre befolkningen blir större växer behovet av att tillhandahålla vård i hemmet. Denna tjänst använder i allmänhet inte systemteori. Eftersom fler människor kommer att behöva hemtjänst kommer det att finnas behov av att öka effektiviteten samtidigt som kvaliteten hålls hög. Syftet med denna avhandling är att undersöka hur vi kan använda systemteori och optimering inom hemtjänst samt definiera hur vi kan modellera kvaliteten och använda dessa kvalitetsparametrar för att erbjuda bästa möjliga service. Modellen använder VRP med Time windows för att schemalägga rutterna och inkorporerar servicebehov hos kunderna. En lösning erhålles genom att först bygga en initial lösning. Sedan använder den en lokal sökning med en dynamisk heuristisk för att förbättra lösningen. Tabu search används som en meta-heuristik för att förhindra att lösningen fastnar i lokala minima. Algoritmen används för att optimera kvalitetsparametrarna. Resultatet kan användas för att hjälpa leverantörer av hemtjänst att bestämma vilken kvalitetsnivå de kan leverera med en begränsad budget

Downstream vehicles detect an emergency response vehicle (ERV) through sirens and/or strobe lights. These traditional warning systems do not give any recommendation about how to react, leaving the drivers confused and often adopting unsafe behavior while trying to open a passage for the ERV. In this research, an advanced intra-link emergency assistance system, that leverages the emerging technologies of the connected vehicle environment, is proposed. The proposed system assumes the presence of a centralized system that gathers/disseminates information from/to connected vehicles via vehicle-to-infrastructure (V2I) communications. The major contribution of this dissertation is the intra-link level support provided to ERV as well as non-ERVs. The proposed system provides network-wide assistance as it also considers the routing of ERVs. The core of the system is a mathematical program - a set of equations and inequalities - that generates, based on location and speed data from connected vehicles that are downstream of the ERV, the fastest intra-link ERV movement. It specifies for each connected non-ERV a final assigned position that the vehicle can reach comfortably along the link. The system accommodates partial market penetration levels and is applicable on large transportation link segments with signalized intersections. The system consists of three modules (1) an ERV route generation module, (2) a criticality analysis module and (2) the sequential optimization module. The first module determines the ERV's route (set of links) from the ERV's origin to the desired destination in the network. Based on this selected route, the criticality analysis module scans/filters the connected vehicles of interest and determines whether any of them should be provided with a warning/instruction message. As the ERV is moving towards its destination, new non-ERVs should be notified. When a group of non-ERVs is identified by the criticality analysis module, a sequential optimization module is activated. The proposed system is evaluated using simulation under different combinations of market penetration and congestion levels. Benefits in terms of ERV travel time with an average reduction of 9.09% and in terms of vehicular interactions with an average reduction of 35.46% and 81.38% for ERV/non-ERV and non-ERV/non-ERV interactions respectively are observed at 100% market penetration, when compared to the current practice where vehicles moving to the nearest edge. / Doctor of Philosophy / Downstream vehicles detect an emergency response vehicle (ERV) through sirens and/or strobe lights. These traditional warning systems do not give any recommendations about how to react, leaving the drivers confused and often adopting unsafe behavior while trying to open a passage for the ERV. In this research, an advanced intra-link emergency assistance system, that leverages the emerging technologies of the connected vehicle environment, is proposed. The proposed system assumes the presence of a centralized system that gathers/disseminates information from/to connected vehicles via vehicle-to-infrastructure (V2I) communications. The major contribution of this dissertation is the intra-link level support provided to ERV as well as non-ERVs. The proposed system provides network-wide assistance as it also considers the routing of ERVs. The core of the system is a mathematical program - a set of equations and inequalities - that generates, based on location and speed data from connected vehicles that are downstream of the ERV, the fastest intra-link ERV movement. It specifies for each connected non-ERV a final assigned position that the vehicle can reach comfortably along the link. The system accommodates partial market penetration levels and is applicable on large transportation link segments with signalized intersections. The system consists of three modules (1) an ERV route generation module, (2) a criticality analysis module and (2) the sequential optimization module. The first module determines the ERV’s route (set of links) from the ERV’s origin to the desired destination in the network. Based on this selected route, the criticality analysis module scans/filters the connected vehicles of interest and determines whether any of them should be provided with a warning/instruction message. As the ERV is moving towards its destination, new non-ERVs should be notified. When a group of non-ERVs is identified by the criticality analysis module, a sequential optimization module is activated. The proposed system is evaluated using simulation under different combinations of market penetration and congestion levels. Benefits in terms of ERV travel time with an average reduction of 9.09% and in terms of vehicular interactions with an average reduction of 35.46% and 81.38% for ERV/non-ERV and non-ERV/non-ERV interactions respectively are observed at 100% market penetration, when compared to the current practice where vehicles moving to the nearest edge.

<p> In this thesis, we have considered the vehicle routing problem with pickup and delivery which is a generalization of the capacitated vehicle routing problem (CVRP). The vehicle routing problem with pickup and delivery (VRPPD) arises whenever pickup demand and delivery demand is to be satisfied by the same vehicle. The problem is encountered in many real life situations including reverse logistics. We consider three variants of VRPPD, namely, the vehicle routing problem with back-hauls (VRPB), the vehicle routing problem with back-hauls and mixed-load (VRPBM) and the vehicle routing problem with simultaneous pickup and delivery (VRPSPD). </p> <p> The inherent complexity of VRPPD makes it an NP -hard problem. It is not possible to solve an NP-hard problem in polynomial time unless P = NP. Therefore, heuristics and metaheuristics are used to produce a good quality solution within reasonable CPU time. We develop ant colony algorithms for VRPB, VRPBM and VRPSPD. We have improved the existing ant-colony algorithms by applying better local search schemes and by adding new features such as construction rule and the trail updating criteria. We also develop saving based heuristics for single and multi-depot versions of VRPSPD. Checking feasibility of a given route is an important issue in VRPSPD because of the fluctuating load on the vehicle. We have proposed the cumulative net-pickup approach for this purpose. One important feature of this approach is that it checks the feasibility of an altered route in constant time. </p> <p> The proposed heuristics and metaheuristics are evaluated by solving benchmark problem instances available in literature and then comparing the solutions with the solutions produced by the existing algorithms. Our computational experiment has shown that the proposed heuristics and metaheuristics give better or equally good results in comparison to the existing solution procedures. </p> / Thesis / Doctor of Philosophy (PhD)

Vehicle Routing Problems are optimization problems centered around determining optimal travel routes for a fleet of vehicles to visit a set of nodes. Optimality is evaluated with regard to some desired quality of the solution, such as time-minimizing or cost-minimizing. There are many established solution methods which makes it meaningful to compare their performance. This thesis aims to investigate how the performances of various solution methods is affected by varying certain problem parameters. Problem characteristics such as the number of customers, vehicle capacity, and customer demand are investigated. The aim was approached by dividing the problem into two subproblems: distributing the nodes into suitable clusters, and finding the shortest route within each cluster. Results were produced by solving simulated sets of customers for different parameter values with different clustering methods, namely sweep, k-means and hierarchical clustering. Although the model required simplifications to facilitate the implementation, theresults provided some significant findings. The thesis concludes that for large vehicle capacity in relation to demand, sweep clustering is the preferred method. Whereas for smaller vehicles, the other two methods perform better.

The vehicle routing problem (VRP) determines preferred vehicle routes to visit multiple customer locations from a depot location based on a defined objective function. The VRP is an NP-hard network optimization problem that is challenging to solve to optimality. Over the past 60 years, multitudes of heuristics and metaheuristics have been developed in order to minimize the computational burden of solving the VRP. In order to compare the performance of VRP heuristics, researchers have developed bench-marking datasets. These datasets, however, lack properties found in industry datasets. In this dissertation, we explore how properties of industry datasets influence VRP heuristics and objective functions. In Chapter 2, we quantify and compare features of bench-marking and industry datasets. In order to determine if these features influence heuristic performance, we conduct extensive computational runs on three heuristics, Tabu Search, Genetic Algorithm, and Clarke-Wright Savings Procedure, on standard and industry datasets. In Chapter 3, we derive worst-case analysis on how VRP objective functions and metrics relate to one another. These bounds depend on properties of customer locations. These bounds illustrate how customer locations can influence how different routes behave for different routing metrics. Finally, in Chapter 4, we improve two VRP heuristics, Clarke-Wright Saving Procedure and Hybrid Genetic Search Algorithm, by developing new enhancements to the algorithms. These enhancements rely on certain properties of the datasets in order to perform well. Thus, these heuristics perform better on specific VRP dataset types. / Doctor of Philosophy / The vehicle routing problem (VRP) creates vehicle routes that have the shortest travel distance. The routes determine how vehicles should visit multipl customer locations, to deliver or pickup goods, and return to a depot location. While explaining what the VRP entails is simple, the VRP is actually very difficult for even the most sophisticated algorithms on the best computers to solve. Over the past 60 years, many algorithms have been developed in order to more easily and quickly solve the VRP. In order to compare the performance of VRP algorithms, researchers have developed bench-marking datasets. However, these datasets lack properties of datasets found in industry. In this dissertation, we look to connect the disconnect between industry and bench-marking datasets by 1) comparing feature differences between these two types of datasets, 2) determining if differences in datasets imply differences in algorithm performance, 3) proving how problem differences influence VRP routes, and 4) enhancing existing VRP algorithms to perform better on specific VRP dataset types.

In this dissertation, the vehicle routing problem and one of its variants, the vehicle routing problem with simultaneous pick up and deliveries (VRPSPD) are studied. The traditional vehicle routing problem (VRP) consists of constructing minimum cost routes for the vehicles to follow so that the set of customers are visited only once. A lot of effort has been devoted to research on developing fast and effective solution methods for many different versions of this problem by different majors of engineering profession. Thus, a structuring effort is needed to organize and document the vast literature so far has accumulated in this field. Over its lifespan the VRP literature has become quite disjointed and disparate. Keeping track of its development has become difficult because its subject matter transcends several academic disciplines and professions that range from algorithm design to traffic management. Consequently, this dissertation begins with defining VRP's domain in its entirety, accomplishes an allencompassing taxonomy for the VRP literature, and delineates all of VRP's facets in a parsimonious and discriminating manner. Sample articles chosen for their disparity are classified to illustrate the descriptive power and parsimony of the taxonomy. Next, a more detailed version of the original problem, the VRPSPD is examined and a more abstract taxonomy is proposed. Additionally, two other existing classification methodologies are used to distinguish all published VRPSPD papers on their respective research strategies and solution methods. By using well-organized methods this study provides a solid multidimensional identification of all VRPSPD studies? attributes thus synthesizing knowledge in the filed. Finally, a hybrid metaheuristic solution algorithm for the VRPSPD problem is presented. To solve this NP-hard vehicle routing problem a GRASP initiated hybrid genetic algorithm is developed. The algorithm is tested on two sets of benchmark problems from the literature with respect to computational efficiency and solution quality. The effect of starting with a better initial population for the genetic algorithm is further investigated by comparing the current results with previously generated ones. The experimental results indicate that the proposed algorithm produces relatively good quality solutions and a better initial population yields a reduction in processing cycles.