There are different transportations in the city logistics (e.g., passengers, freights, and wastes), which are handled respectively by single-purpose vehicles (SVs) of the corresponding type. The multi-purpose vehicle (MV) is a future concept whose load modules can be changed for different urban transportations. MVs enable the sequential sharing of different mobilities, thus theoretically improving the efficacy of the city logistics by higher utilization of vehicles. A variant model of the Pick-up and Delivery Problem with Time Windows is established to describe the sequential sharing problem considering both MVs and SVs with the features of multiple depots, partial recharging strategies, and fleet sizing. In the problem, MVs can change their load modules for all types of objects carried by SVs. An adaptive large neighborhood algorithm (ALNS) is developed with new mechanisms for MVs. The proposed ALNS is tested by 15 artificial data cases and compared with the MIP solver. The results show the proposed ALNS is time-effective and validated to find good solutions. / Det finns olika transporter i stadslogistiken (t.ex. passagerare, gods och avfall), som hanteras av enskilda fordon (SV) av motsvarande typ. Multifunktionsfordonet (MV) är ett framtida koncept vars lastmoduler kan ändras för olika stadstransporter. MV möjliggör sekventiell delning av olika mobiliteter, vilket på ett teoretiskt sätt förbättrar stadslogistikens effektivitet genom högre användning av fordon. En variantmodell av Pick-up and Delivery Problem with Time Windows är etablerad för att beskriva det sekventiella delningsproblemet med beaktande av både MV och SV med funktionerna i flera depåer, partiella laddningsstrategier och flottans storlek. I problemet kan MV: er ändra sina belastningsmoduler för alla typer av objekt som bärs av SV: er. En adaptiv stor stadsdelalgoritm (ALNS) har utvecklats med nya mekanismer för MV. Den föreslagna ALNS testas av 15 artificiella datafall och jämförs med MIP-lösaren. Resultaten visar att det föreslagna ALNS är tidseffektivt och validerat för att hitta bra lösningar.

<p>Examensarbetet syftar till att jämföra nya alternativ till olika system för användning i laborationer i reglerteknikkurser för olika studentkategorier. Det skall utredas vilket av ett antal alternativ till mjukvaruplattformar som är bäst lämpat att användas vid reglerteknikundervisningen i ITN:s reglerlaboratorium vid Linköpings universitet. Tidigare laborationer i berörda kurser skall även modifieras så att dessa kan genomföras i de nya systemen.</p><p>Examensarbetet resulterade i en rad modifierade laborationer och system att tillämpa i dessa. De nya systemen medför att all reglering sköts direkt från en dator istället för tidigare variant med externa apparater som programmeras. På så sätt kan större fokus läggas på regleringen i sig och inte de system som tillämpas för att utföra den.</p> / <p>The purpose of this thesis work is to compare new alternatives for different systems to use in laborations, in courses offered in control system design, for different types of students. The intention is to investigate which of a number of software platform alternatives are best suited for these purposes. Current laborations are to be modified to be viable in the new systems.</p><p>The project resulted in a number of modified laborations and control systems to use in these. The new solutions are made so that all of the control is done by one computer, as opposed to the previous solution where external units had to be programmed and controlled. This way, the laborations can focus more on the control theory and less on the systems used to realize it.</p>

Examensarbetet syftar till att jämföra nya alternativ till olika system för användning i laborationer i reglerteknikkurser för olika studentkategorier. Det skall utredas vilket av ett antal alternativ till mjukvaruplattformar som är bäst lämpat att användas vid reglerteknikundervisningen i ITN:s reglerlaboratorium vid Linköpings universitet. Tidigare laborationer i berörda kurser skall även modifieras så att dessa kan genomföras i de nya systemen. Examensarbetet resulterade i en rad modifierade laborationer och system att tillämpa i dessa. De nya systemen medför att all reglering sköts direkt från en dator istället för tidigare variant med externa apparater som programmeras. På så sätt kan större fokus läggas på regleringen i sig och inte de system som tillämpas för att utföra den. / The purpose of this thesis work is to compare new alternatives for different systems to use in laborations, in courses offered in control system design, for different types of students. The intention is to investigate which of a number of software platform alternatives are best suited for these purposes. Current laborations are to be modified to be viable in the new systems. The project resulted in a number of modified laborations and control systems to use in these. The new solutions are made so that all of the control is done by one computer, as opposed to the previous solution where external units had to be programmed and controlled. This way, the laborations can focus more on the control theory and less on the systems used to realize it.

近年來隨著全球化的發展，自助旅行的風氣蔚為風潮。背包客可以根據自己的喜好與條件，自己規劃旅遊路線與行程。一般規劃旅遊行程的過程費時而繁瑣，除了必須決定旅遊景點，還必須將景點開放時間、景點停留時間、交通方式、旅遊順序與路線、時間限制、住宿地點、經費等列入考量。 針對旅遊行程規劃，除了參考網友的行程規劃，目前已普遍有景點推薦、行程編輯系統，協助使用者規劃行程。但少有旅遊行程自動規劃系統。因此，本論文研發實作旅遊行程的自動規劃系統MyTripPlan。MyTripPlan具備景點推薦、景點停留與拜訪時間預估、路線規劃、行程規劃及行程調整的功能。 本系統MyTripPlan在離線時，先透過爬蟲程式由景點推薦網站取得熱門景點資訊、由相片分享網站取得景點相片時間以推估景點停留及拜訪時間、由交通查詢網站取得任兩景點間的推估交通時間。在線上時，當使用者輸入旅遊天數等時間限制、並由系統推薦景點勾選有興趣拜訪的景點及餐廳後，系統將運用定向排程演算法推論出符合時間限制的旅遊行程，呈現在地圖上，並結合交通網站，產生行程表。 經實驗效能驗證，以安排旅遊天數七天，五十六個景點所需要的行程規劃時間約為一秒鐘；使用者對於實作完畢的MyTripPlan系統與功能也都有滿意以上的評分。 / Travel planning process is time-consuming and tedious. To plan a trip, not only the attractions, but opening hours, timing cost, travel route, transportation, lodge, budget control and so on also need to be considered. While there are widespread attraction recommendation and itinerary editing systems to assist people to plan their trip, only few trip automated planning systems are developed. In this thesis, MyTripPlan, an automatic trip planning system, is designed and developed. MyTripPlan The system provides users the capability of attraction recommendation, visiting and stay time estimation, route planning, trip planning and itinerary adjustments. In offline process, MyTripPlan collects popular attraction information from web content for attraction recommendation, gets the timestamp of attractions from photo-sharing websites to estimate visiting and stay time, and crawls traffic information from public transportation query site to estimate the travel time between attractions. Given the trip duration, MyTripPlan recommends attractions and restaurants, schedules and produces the trip itinerary automatically based on the team orienteering scheduling algorithm. The generated itinerary takes the user-preferred attractions, visiting and stay time constraints, and transportation information into consideration. MyTripPlan presents the trip itinerary both in map and schedule list. The experiments show that the execution time for trip plan with fifty-six attractions in seven days requires about one second. Moreover, nineteen subjects were invited to evaluate the effectiveness of MyTripPlan. Most users were satisfied and gave excellent rating on the system performance.

Cette thèse porte sur les problèmes de tournées de véhicules avec fenêtres de temps où un gain est associé à chaque client et où l'objectif est de maximiser la somme des gains recueillis moins les coûts de transport. De plus, un même véhicule peut effectuer plusieurs tournées durant l'horizon de planification. Ce problème a été relativement peu étudié en dépit de son importance en pratique. Par exemple, dans le domaine de la livraison de denrées périssables, plusieurs tournées de courte durée doivent être combinées afin de former des journées complètes de travail. Nous croyons que ce type de problème aura une importance de plus en plus grande dans le futur avec l'avènement du commerce électronique, comme les épiceries électroniques, où les clients peuvent commander des produits par internet pour la livraison à domicile. Dans le premier chapitre de cette thèse, nous présentons d'abord une revue de la littérature consacrée aux problèmes de tournées de véhicules avec gains ainsi qu'aux problèmes permettant une réutilisation des véhicules. Nous présentons les méthodologies générales adoptées pour les résoudre, soit les méthodes exactes, les méthodes heuristiques et les méta-heuristiques. Nous discutons enfin des problèmes de tournées dynamiques où certaines données sur le problème ne sont pas connues à l'avance. Dans le second chapitre, nous décrivons un algorithme exact pour résoudre un problème de tournées avec fenêtres de temps et réutilisation de véhicules où l'objectif premier est de maximiser le nombre de clients desservis. Pour ce faire, le problème est modélisé comme un problème de tournées avec gains. L'algorithme exact est basé sur une méthode de génération de colonnes couplée avec un algorithme de plus court chemin élémentaire avec contraintes de ressources. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. Le troisième chapitre propose donc une méthode de recherche adaptative à grand voisinage qui exploite les différents niveaux hiérarchiques du problème (soit les journées complètes de travail des véhicules, les routes qui composent ces journées et les clients qui composent les routes). Dans le quatrième chapitre, qui traite du cas dynamique, une stratégie d'acceptation et de refus des nouvelles requêtes de service est proposée, basée sur une anticipation des requêtes à venir. L'approche repose sur la génération de scénarios pour différentes réalisations possibles des requêtes futures. Le coût d'opportunité de servir une nouvelle requête est basé sur une évaluation des scénarios avec et sans cette nouvelle requête. Enfin, le dernier chapitre résume les contributions de cette thèse et propose quelques avenues de recherche future. / This thesis studies vehicle routing problems with time windows, where a gain is associated with each customer and where the objective is to maximize the total gain collected minus the routing costs. Furthermore. the same vehicle might be assigned to different routes during the planning horizon. This problem has received little attention in the literature in spite of its importance in practice. For example, in the home delivery of perishable goods (like food), routes of short duration must be combined to form complete workdays. We believe that this type of problem will become increasingly important in the future with the advent of electronic services, like e-groceries, where customers can order goods through the Internet and get these goods delivered at home. In the first chapter of this thesis, we present a review of vehicle routing problems with gains, as well as vehicle routing problems with multiple use of vehicles. We discuss the general classes of problem-solving approaches for these problems, namely, exact methods, heuristics and metaheuristics. We also introduce dynamic vehicle routing problems, where new information is revealed as the routes are executed. In the second chapter, we describe an exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles, where the first objective is to maximize the number of served customers. To this end, the problem is modeled as a vehicle routing problem with gains. The exact algorithm is based on column generation, coupled with an elementary shortest path algorithm with resource constraints. To solve realistic instances in reasonable computation times, a heuristic approach is required. The third chapter proposes an adaptative large neighborhood search where the various hierarchical levels of the problem are exploited (i.e., complete vehicle workdays, routes within workdays and customers within routes). The fourth chapter deals with the dynamic case. In this chapter, a strategy for accepting or rejecting new customer requests is proposed. This strategy is based on the generation of multiple scenarios for different realizations of the requests in the future. An opportunity cost for serving a new request is then computed, based on an evaluation of the scenarios with and without the new request. Finally, the last chapter summarizes the contributions of this thesis and proposes future research avenues.

Nous adaptons une heuristique de recherche à voisinage variable pour traiter le problème du voyageur de commerce avec fenêtres de temps (TSPTW) lorsque l'objectif est la minimisation du temps d'arrivée au dépôt de destination. Nous utilisons des méthodes efficientes pour la vérification de la réalisabilité et de la rentabilité d'un mouvement. Nous explorons les voisinages dans des ordres permettant de réduire l'espace de recherche. La méthode résultante est compétitive avec l'état de l'art. Nous améliorons les meilleures solutions connues pour deux classes d'instances et nous fournissons les résultats de plusieurs instances du TSPTW pour la première fois. / We adapt a general variable neighborhood search heuristic to solve the traveling salesman problem with time windows (TSPTW) where the objective is to minimize the completion time. We use efficient methods to check the feasibility and the profitability of a movement. We use a specific order to reduce the search space while exploring the neighborhoods. The resulting method is competitive with the state-of-the-art. We improve the best known solutions for two classes of instances and provide the results of multiple instances of TSPTW for the first time.

Cette thèse porte sur les problèmes de tournées de véhicules avec fenêtres de temps où un gain est associé à chaque client et où l'objectif est de maximiser la somme des gains recueillis moins les coûts de transport. De plus, un même véhicule peut effectuer plusieurs tournées durant l'horizon de planification. Ce problème a été relativement peu étudié en dépit de son importance en pratique. Par exemple, dans le domaine de la livraison de denrées périssables, plusieurs tournées de courte durée doivent être combinées afin de former des journées complètes de travail. Nous croyons que ce type de problème aura une importance de plus en plus grande dans le futur avec l'avènement du commerce électronique, comme les épiceries électroniques, où les clients peuvent commander des produits par internet pour la livraison à domicile. Dans le premier chapitre de cette thèse, nous présentons d'abord une revue de la littérature consacrée aux problèmes de tournées de véhicules avec gains ainsi qu'aux problèmes permettant une réutilisation des véhicules. Nous présentons les méthodologies générales adoptées pour les résoudre, soit les méthodes exactes, les méthodes heuristiques et les méta-heuristiques. Nous discutons enfin des problèmes de tournées dynamiques où certaines données sur le problème ne sont pas connues à l'avance. Dans le second chapitre, nous décrivons un algorithme exact pour résoudre un problème de tournées avec fenêtres de temps et réutilisation de véhicules où l'objectif premier est de maximiser le nombre de clients desservis. Pour ce faire, le problème est modélisé comme un problème de tournées avec gains. L'algorithme exact est basé sur une méthode de génération de colonnes couplée avec un algorithme de plus court chemin élémentaire avec contraintes de ressources. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. Le troisième chapitre propose donc une méthode de recherche adaptative à grand voisinage qui exploite les différents niveaux hiérarchiques du problème (soit les journées complètes de travail des véhicules, les routes qui composent ces journées et les clients qui composent les routes). Dans le quatrième chapitre, qui traite du cas dynamique, une stratégie d'acceptation et de refus des nouvelles requêtes de service est proposée, basée sur une anticipation des requêtes à venir. L'approche repose sur la génération de scénarios pour différentes réalisations possibles des requêtes futures. Le coût d'opportunité de servir une nouvelle requête est basé sur une évaluation des scénarios avec et sans cette nouvelle requête. Enfin, le dernier chapitre résume les contributions de cette thèse et propose quelques avenues de recherche future. / This thesis studies vehicle routing problems with time windows, where a gain is associated with each customer and where the objective is to maximize the total gain collected minus the routing costs. Furthermore. the same vehicle might be assigned to different routes during the planning horizon. This problem has received little attention in the literature in spite of its importance in practice. For example, in the home delivery of perishable goods (like food), routes of short duration must be combined to form complete workdays. We believe that this type of problem will become increasingly important in the future with the advent of electronic services, like e-groceries, where customers can order goods through the Internet and get these goods delivered at home. In the first chapter of this thesis, we present a review of vehicle routing problems with gains, as well as vehicle routing problems with multiple use of vehicles. We discuss the general classes of problem-solving approaches for these problems, namely, exact methods, heuristics and metaheuristics. We also introduce dynamic vehicle routing problems, where new information is revealed as the routes are executed. In the second chapter, we describe an exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles, where the first objective is to maximize the number of served customers. To this end, the problem is modeled as a vehicle routing problem with gains. The exact algorithm is based on column generation, coupled with an elementary shortest path algorithm with resource constraints. To solve realistic instances in reasonable computation times, a heuristic approach is required. The third chapter proposes an adaptative large neighborhood search where the various hierarchical levels of the problem are exploited (i.e., complete vehicle workdays, routes within workdays and customers within routes). The fourth chapter deals with the dynamic case. In this chapter, a strategy for accepting or rejecting new customer requests is proposed. This strategy is based on the generation of multiple scenarios for different realizations of the requests in the future. An opportunity cost for serving a new request is then computed, based on an evaluation of the scenarios with and without the new request. Finally, the last chapter summarizes the contributions of this thesis and proposes future research avenues.

This paper deals with optimal distribution issues. One may find listed problems of real life linked to distribution. Moreover, there are explained travelling salesman problem, vehicle routing problem and its variants. This work brings an overview of different ways how to solve vehicle routing problem. In practical part, there is an analysis of distribution of real company. The concept of application is presented in the second part of this paper. This concept could reduce costs of distribution in analyzed company. Testing is aimed mainly on the variant VRPCL (Vehicle Routing Problem with Continuos Loading).

Cette thèse s’intéresse au problème classique de tournées de véhicules avec contraintes de capacité (CVRP pour Capacitated Vehicle Routing Problem) ainsi qu’une variante beaucoup plus complexe, soit le problème de tournées de véhicules dépendant du temps avec fenêtres de temps et points de transfert défini sur un réseau routier (TDVRPTWTP-RN pour Time-Dependent Vehicle Routing Problem with Time Windows and Transfer Points on a Road Network). Dans le premier article, le TDVRPTWTP-RN est résolu en adaptant une métaheuristique qui représente l’état de l’art pour le CVRP, appelé Slack Induction for String Removals (SISR). Cette métaheuristique fait appel au principe “détruire et reconstruire” en retirant des séquences de clients consécutifs dans les routes de la solution courante et en réinsérant ensuite ces clients de façon à créer une nouvelle solution. Le problème est défini sur un réseau routier où différents chemins alternatifs peuvent être utilisés pour se déplacer d’un client à l’autre. De plus, le temps de parcours sur chacun des arcs du réseau n’est pas fixe, mais dépend du moment où le véhicule quitte le sommet origine. S’inspirant de problèmes rencontrés en logistique urbaine, nous considérons également deux types de véhicules, de petite et grande capacité, où les grands véhicules sont interdits de passage au centre-ville. Ainsi, les clients du centre-ville ne peuvent être servis que suite au transfert de leur demande d’un grand à un petit véhicule à un point de transfert. Comme un point de transfert n’a pas de capacité, une problématique de synchronisation apparaît quand un grand véhicule doit y rencontrer un ou plusieurs petits véhicules pour leur transférer une partie de son contenu. Contrairement aux problèmes stricts de tournées de véhicules à deux échelons, les grands véhicules peuvent aussi servir des clients localisés à l’extérieur du centre-ville. Comme le problème abordé est beaucoup plus complexe que le CVRP, des modifications importantes ont dû être apportées à la métaheuristique SISR originale. Pour évaluer la performance de notre algorithme, un ensemble d’instances tests a été généré à partir d’instances existantes pour le TDVRPTW-RN. Les réseaux omt été divisés en trois régions : centre-ville, frontière et extérieur. Le centre-ville et l’extérieur sont respectivemnt les royaumes des petits et grands véhicules, tandis que la frontière (où l’on retrouve les points de transfert) peut être visité par les deux types de véhicules. Les résultats numériques montrent que la métaheuristique proposée exploite les opportunités d’optimiser une solution en déplaçant autant que possible les clients neutres, soit ceux qui peuvent être servis indifféremment par un petit ou un grand véhicule, des routes des petits véhicules vers les routes des grands véhicules, réduisant ainsi les coûteuses visites aux points de transfert. Les deuxième et troisième article s’intéressent à des concepts plus fondamentaux et font appel au problème plus simple du CVRP pour les évaluer. Dans le second article, un étude expérimentale est conçue afin d’examiner l’impact de données (distances) imprécises sur la performance de différents types d’heuristiques, ainsi qu’une méthode exacte, pour le CVRP. À cette fin, différents niveaux d’imprécision ont été introduits dans des instances tests classiques pour le CVRP avec 100 à 1 000 clients. Nous avons observé que les meilleures métaheuristiques demeurent les meilleures, même en présence de hauts niveaux d’imprécision, et qu’elles ne sont pas affectées autant par les imprécisions qu’une heuristique simple. Des expériences avec des instances réelles ont mené aux mêmes conclusions. Le troisième article s’intéresse à l’intégration de l’apprentissage automatique dans la métaheuristique SISR qui représente l’état de l’art pour le CVRP. Dans ce travail, le principe “détruire et reconstruire” au coeur de SISR est hybridé avec une méthode d’apprentissage par renforcement qui s’inspire des systèmes de colonies de fourmis. L’ap- prentissage automatique a pour but d’identifier les arêtes les plus intéressantes, soit celles qui se retrouvent le plus fréquemment dans les solutions de grande qualité précédemment rencontrées au cours de la recherche. L’inclusion de telles arêtes est alors favorisé lors de la réinsertion des clients ayant été retirés de la solution par le mécanisme de destruction. Les instances utilisées pour tester notre approche hybride sont les mêmes que celles du second article. Nous avons observé que notre algorithme ne peut produire que des solutions lé- gèrement meilleures que la métaheuristique SISR originale, celle-ci étant déjà quasi-optimale. / This thesis is concerned both with the classical Capacitated Vehicle Routing Problem (CVRP) and a much more complex variant called the Time-Dependent Vehicle Routing Problem with Time Windows and Transfer Points on a Road Network (TDVRPTWTP-RN ). In the first paper, the TDVRPTWTP RN is solved by adapting a state-of-the-art metaheuris- tic for the CVRP, called Slack Induction for String Removals (SISR). This metaheuristic is based on the ruin and recreate principle and removes strings of consecutive customers in the routes of the current solution and then reinserts the removed customers to create a new solution. The problem is formulated in a full road network where different alternative paths can be used to go from one customer to the next. Also, the travel time on each arc of the road network is not fixed, but depends on the departure time from the origin node. Motivated from city logistics applications, we also consider two types of vehicles, large and small, with large vehicles being forbidden from the downtown area. Thus, downtown customers can only be served through a transfer of their goods from large to small vehicles at designated transfer points. Since transfer points have no capacity, synchronization issues arise when a large vehicle must meet one or more small vehicles to transfer goods. As opposed to strict two-echelon VRPs, large vehicles can also directly serve customers that are outside of the downtown area. Given that the TDVRPTWTP-RN is much more complex than the CVRP, important modifications to the original SISR metaheuristic were required. To evaluate the performance of our algorithm, we generated a set of test instances by extending existing instances of the TDVRPTW-RN . The road networks are divided into three regions: downtown, boundary and outside. The downtown and outside areas are the realm of small and large vehicles, respectively, while the boundary area that contains the transfer points can be visited by both small and large vehicles. The results show that the proposed metaheuristic exploits optimization opportunities by moving as much as possible neutral customers (which can be served by either small or large vehicles) from the routes of small vehicles to those of large vehicles, thus avoiding costly visits to transfer points. The second and third papers examine more fundamental issues, using the classical CVRP as a testbed. In the second paper, an experimental study is designed to examine the impact of inaccurate data (distances) on the performance of different types of heuristics, as well as one exact method, for the CVRP. For this purpose, different levels of distance inaccuracies were introduced into well-known benchmark instances for the CVRP with 100 to 1,000 customers. We observed that the best state-of-the-art metaheuristics remain the best, even in the presence of high inaccuracy levels, and that they are not as much affected by inaccuracies when compared to a simple heuristic. Some experiments performed on real-world instances led to the same conclusions. The third paper focuses on the integration of learning into the state-of-the-art SISR for the CVRP. In this work, the ruin and recreate mechanism at the core of SISR is enhanced by a reinforcement learning technique inspired from ant colony systems. The learning component is aimed at identifying promising edges, namely those that are often found in previously encountered high-quality solutions. The inclusion of these promising edges is then favored during the reinsertion of removed customers. The benchmark instances of the second paper were also used here to test the new hybrid algorithm. We observed that the latter can produce only slightly better solutions than the original SISR, due to the quasi-optimality of the original solutions.