Keywords: Mot clés: Logistique urbaine, Bus de fret, Problème de tournée de véhicule, Logistique collaborative, Optimisation combinatoire, Programmation mathématique, Métaheuristiques Key words: Urban logistics, Freight Bus, Vehicle Routing Problem, Collaborative logistics, Combinatorial optimization, Mathematical programming, Meta-heuristics

Dans cette thèse, les bus de fret sont introduits comme un nouveau moyen de transport collectif pour la logistique urbaine. Tout comme les bus, les bus de fret sont des véhicules normalisés avec les itinéraires et les horaires fixes. Grace aux services stables et précis fournis par ces bus de fret, les expéditeurs et les consommateurs peuvent organiser de manière flexible les délais de livraison et de ramassage de leurs commandes.

Le problème de planification d'itinéraires de bus de fret pour la distribution urbaine est étudié, où chaque bus de fret effectue répétitivement un circuit partant d'un centre de distribution, se rendant à plusieurs dépôts et retournant au centre. Ce problème est une nouvelle variante du problème de tournées périodiques de véhicules, qui n'a jamais été étudiée dans la littérature. Nous avons étudié trois variantes du problème de planification d'itinéraires de bus de fret : le problème de base avec demandes de livraison uniquement, le problème avec ramassages et livraisons, et le problème avec demandes de ramassage et de livraison stochastiques. Pour chaque variante du problème, après avoir établi un modèle mathématique, nous avons développé un algorithme méta-heuristique pour la résoudre. Le choix de chaque algorithme prend en compte les caractéristiques de la variante correspondante du problème étudiée. La pertinence des modèles et l'efficacité des algorithmes proposés sont prouvées par des expérimentations numériques intensives.

China Scholarship Council (CSC) and the project TCDU (Collaborative Transportation in Urban Distribution) of the ANR (French Research Agent). This project is labelled by 'Pôle Véhicule du Futur', and is jointly performed by four partners, three French Universities of Technology (UTT, UTBM, UTC) and a startup Share And Move Solutions (SAMs).

This work has been accomplished under the supervision of Prof. Haoxun CHEN and Prof. Farouk YALAOUI. I would like to express my deepest gratitude to them for their highly valuable guidance and incessant support. I highly appreciate the friendly environment created during my three and a half year study. The high confidence they have given to me is the greatest reward of my endeavors.

I also would like to express my special thanks to Mr. Hamid ALLAOUI and Mme.

Marie-Ange MANIER for accepting the review of my PhD thesis, and Mr. Lionel AMODEO and Mr. Yunfeng MA for agreeing to examine this thesis.

I would like to thank all researchers, secretaries and colleagues in LOSI, and the staffs of the doctoral school of UTT for their helps given to me in the past three and a half years.

I would like to thank all my friends, Dr. Yuan LI, Dr. Xixi WANG, Dr. Bo DAI, Dr. Tong QIAO, Prof. Qingxian AN, Dr. Shijian WANG, Dr. Jinrui MA, Dr. Beibei XIONG, Dr. Binbin WANG, Dr. Zhang NA, for their helpful suggestions and encouragement during my stay in France.

Most of all, I would like to thank my parents for their supports, encouragements, and loves given to me in all my life.

List of figures

General Introduction

Research background

More than half of the population in the world currently lives in urban areas. The World Health Organization predicts that the population in urban areas will continue to expand by more than 1.5% per year until 2030 [START_REF] Who | Hidden cities: Unmasking and overcoming health inequities in urban settings[END_REF]. The likely consequences of this expansion are more traffic congestion, pollution, and noise, but also larger customer bases and business opportunities due to the economies of scale. Moving cargos between and within cities while preserving the residents' high quality of life is a key challenge for city planners and logistics service providers.

Logistics and transportation enable economic development, but they are traditionally quite inefficient in urban areas. As shown in [START_REF] Rose | Urban logistics: Establishing key concepts and building a conceptual framework for future research[END_REF] , urban areas are characterized by the interplay of stakeholders with different interests in close quarters, and, as highlighted in [START_REF] Kin | Sustainable urban freight transport in megacities in emerging markets[END_REF], megacities add growing sustainability challenges. Further obstacles include low load factors, empty trips, long dwell times at loading and unloading points, and large numbers of deliveries to individual customers [START_REF] Cepolina | A new urban freight distribution scheme and an optimization methodology for reducing its overall cost[END_REF]. The challenges and obstacles make us to rethink the way that the existing infrastructures are used and how new infrastructures are built, so that they are fully utilized and negative externalities are minimized.

Surveys over existing logistics systems [START_REF] Finnegan | Urban freight in Dublin city center, Ireland: Survey analysis and strategy evaluation[END_REF][START_REF] Dablanc | Goods transport in large European cities: Difficult to organize, difficult to modernize[END_REF] suggest that the provision of logistics services is inappropriate to the growing demand.

In the past decades, many efforts have been made to optimize various logistics systems in industries to operate more efficiently. Some logistics planning strategies have been proposed to promote the performance of goods transportation services in urban areas.

An organizational and technological framework for the integrated management of Chapter 1. General Introduction urban freight transportation was proposed and some planning issues were addressed in [START_REF] Crainic | Advanced freight transportation systems for congested urban areas[END_REF]. Some logistics measures to regulate freight transportation and logistics systems, frequently found in European cities, were classified and evaluated with expected goals [START_REF] Russo | Measures for sustainable freight transportation at urban scale: expected goals and tested results in Europe[END_REF]. A logistics hub model and system framework for Special Economic Trade Zones was designed and analyzed in [START_REF] Trappey | SETZ logistics models and system framework for manufacturing and exporting large engineering assets[END_REF].

One effective way to reduce logistics costs is the collaboration among businesses, logistics service providers, citizens, and the public sector. By working together, multiple actors or stakeholders increase their efficiency through sharing resources, such as vehicles, cargo consolidation or distribution centers, or last-mile delivery services.

Collaboration could potentially lead to fewer vehicles in urban areas, less pollution, and lower logistics costs for the delivery of goods. In 1973, Japanese scholar Shize (1973) first put forward the joint distribution which has been proved to be an effective way for urban logistics. Joint distribution promotes enterprises with similar functions to use common facilities and equipment such as warehouses, logistics platforms, and vehicles, through which small orders of goods for delivery can be consolidated into a largevolume distribution order to achieve the economics of scale in transportation and other logistics services. [START_REF] Gill | Co-operation in channels of distribution: physical distribution leads the way[END_REF] pointed out that members of a distribution channel should cooperate with each other through joint distribution, and illustrated the effectiveness of joint distribution, and proposed several principles for implementing it. [START_REF] Hao | The research on joint distribution mode of the chain retail enterprises[END_REF] discussed the basic concepts and operation models of joint distribution in urban logistics. [START_REF] Xu | Research on joint distribution cost allocation model[END_REF] proposed a model for cost sharing among small companies implementing joint distribution.

Through a large number of literature and industry observations, we can see that the main issues faced by urban logistics at present are as follows: Firstly, the infrastructure of urban logistics needs to be upgraded and transformed. Secondly, the quality and efficiency of the "last mile" service in urban logistics needs to be improved.

Thirdly, Various logistics companies still lack cooperation. Fourthly, the urban logistics needs to improve its own mechanization and informatization level. Fifthly, The government needs to make unified planning and management for the healthy development of urban logistics.

In response to these issues in urban logistics, in this thesis we put forward for the first time the concept of freight bus in urban distribution and study the route planning problem of freight buses. The introduction of a freight bus system in an urban area can Chapter 1. General Introduction realize joint distribution of multiple shippers and help us to solve some problems in "last mile" logistics.

Problems studied in this thesis and main contributions

As we described in the last section, with the rapid development of e-commerce and urbanization, more and more city freighters operated by different private third-party logistics companies were born and circulate in the centers of cities, which makes traffic congestions and air pollutions more and more severe in metropolitan areas. This makes the traffic control for city freighters more difficult to be implemented on the one hand, and makes the delivery time windows of e-commerce orders more difficult to be respected on the other hand [START_REF] Amaral | Urban logistics and Traffic Management: Modelling the Inner and Outer Urban Transport Flows in a Two-Tiered System[END_REF]. To reduce traffic congestions and improve the efficiency and time accuracy of delivery, it needs more collaboration among third-party logistics companies (carriers) in urban distribution Motivated by joint distribution, in this thesis, we put forward for the first time the concept of freight bus, which is a new public transportation means for urban logistics that can replace city freighters belonging to different private third-party logistics companies in the center of a metropolitan city such as Beijing and Paris. Just like buses for passengers, freight buses can be also run by the city government and provide a public service for urban logistics. Because of their utilization shared by all suppliers who want to deliver its goods to their customers, we can expect that the freight buses have some advantages compared with city freighters. Firstly, the freight buses can realize joint distribution of different third-party logistics companies, and can thus save urban logistics costs and reduce the air pollution; Secondly, because of having a regular schedule, the freight buses can improve the timeliness and accuracy of logistics services; Thirdly, replacing private city freighters by freight buses can facilitate the traffic control in a city and reduce the traffic congestion. Finally, the freight buses can improve the utilization rate of special lanes reserved for buses.

The road transportation by vehicles is the most important part of many logistics systems, and the route optimization of vehicles has been a hot research topic for many scholars in the field of operations research and management science all over the world.

In this thesis, we also study the route planning problem of freight buses in an urban distribution system. In the problem, each freight bus has a fixed route, it repeatedly performs a tour that leaves from a distribution center (DC), visits multiple depots, and returns to the DC. All depots in the system are visited by multiple freight buses with the same visiting frequency. The route planning problem can be considered a new variant of periodic vehicle routing problem. To the best of our knowledge, buses dedicated to the transportation of freight were rarely addressed in the literature and the freight bus routing problem considered in this thesis was never studied by other researchers. Considering different real scenarios, this thesis has studied three variants of freight bus routing problem: the basic freight buses routing problem with only delivery, the freight buses routing problem with both pickup and delivery, the freight buses routing problem with stochastic pickup and delivery demands. For each variant of the freight buses routing problem, we establish a mathematical model and propose a metaheuristic algorithm to solve it. The choice of each algorithm considers the characteristics of the corresponding problem. The relevance of the mathematical models and the effectiveness of the proposed algorithms are proved by numerical experiments. The main research contents of this thesis are as follows: After presenting three-level urban distribution systems existing in big cities, Chapter 3 innovatively puts forward the concept of freight bus system for the urban distribution in the second level, so as to use freight buses to replace existing city freighters dispersedly running in a city center. This chapter then describes the infrastructure and operation management of the freight bus distribution system after conducting a macroscopic analysis of the advantages of the freight bus in collaborative transportation, timely distribution, increase of road utilization and other aspects in comparison with city freighters.

Chapter 4 studies the basic freight bus routing problem with only delivery. After an analysis of the characteristics of the problem and the literature of vehicle routing problems, we recognize this problem is a new variant of periodic vehicle routing problem. The problem is first described under some assumptions on the operation of freight buses and a Mixed-Integer Linear Programming (MILP) model is then formulated for it. In order to solve the problem, a memetic algorithm (genetic algorithm with local search) is developed. The relevance of the mathematical model and the effectiveness of the proposed memetic algorithm are proved by numerical experiments.

Chapter 5 extends the work of Chapter 4. Since in practice, freight buses may perform both pickup and delivery of goods at every customer/supplier location they visit, we further study the route planning problem of freight buses with simultaneous Chapter 1. General Introduction delivery and pickup. As in Chapter 4, the problem is first described under some assumptions. In order to solve the problem, a Mixed-Integer Linear Programming (MILP) model is formulated and an Adaptive Large Neighborhood Search (ALNS) algorithm is developed, which considers the characteristics of the problem. The validity of the model and the effectiveness of our ALNS algorithm are also verified through numerical experiments.

Chapter 4 and Chapter 5 both study the route planning of freight buses with deterministic demands. But in practice, when we make the route planning, the delivery demand and pickup demand at each station in each time period of each day may be not known, although we can obtain the probabilistic distributions of these demands by statistical analysis of their historical data. So in chapter 6 we study the route planning problem of freight buses with stochastic pickup and delivery demands. By adopting the scenario approach, this stochastic optimization problem is formulated as a deterministic equivalent mixed integer linear programming model, and an immune genetic algorithm combined with scenario-based optimization is then developed to solve the problem. The effectiveness of the proposed algorithm is proved by numerical experiments.

The results of the research work of this thesis have been published in the proceedings of international conferences and submitted to international journals as given below.

Conference papers:

Chang,Z., Chen,H., & Yalaoui,F.(2017).Freight Buses in Three-Tiered Distribution Systems for City Logistics: Modeling and Evaluation. 7th IESM Conference, October 11 -13,Saarbrucken,Germany.

Chang,Z., Chen,H., & Yalaoui,F.(2019).Modeling and Evaluation of a City Logistics System with Freight Buses. 8th ICORES 2019,February 19-20,Prague,Czech.

Journal articles:

Chang,Z., Chen,H., & Yalaoui,F., Model and algorithm for route planning of freight buses. Submitted to Computer and Industry Engineer in 2018, revised and under the second round of review.

Chang,Z., Chen,H., Dai,B., & Yalaoui,F. Adaptive large neighborhood search algorithm for route planning of freight buses with pickup and delivery. Submitted to Journal of Industrial and Management Optimization in 2018, revised and under the second round of review.

Chapter 1. General Introduction

Significance of this research

Accompanied with the development of urban logistics, this thesis puts forward a freight bus system as a mean of the urban fret distribution, and studies the routing problem of freight buses under different circumstances. This research has a practical and theoretical significance.

1) From the application perspective, the introduction of freight buses provides new opportunities for a city government and logistics enterprises to improve logistics services to suppliers (manufacturers) and customers while reducing logistics costs and negative environment impact of urban fret distribution.

2) Secondly, from the perspective of logistics enterprises, first of all, the freight bus is a kind of collaborative transportation distribution scheme for logistics enterprises.

The collaborative transportation of freight bus can help logistics enterprises solve the problem of "last mile" for urban distribution to further help the logistics companies improve work efficiency, reduce distribution costs, and acquire greater profits.

Secondly, for suppliers and e-commerce companies, the research of freight bus will be conducive to improve the service level of the logistics system, and further to promotion of the development of those enterprises.

3) Thirdly, from the customer's point of view, because of having a regular schedule, the use of freight buses can improve the timeliness and accuracy of logistics services.

The smooth handover of goods from the supplier to the customer is the basic need to ensure the normal operation of the customer's life. In the e-commerce environment, if the goods purchased by the customer are not delivered to the customer in time, it may affect the normal life of the customer, and cause their dissatisfaction with the ecommerce enterprise and the express delivery enterprise. The freight bus will operate periodically and has an operational schedule to ensure that goods will be delivered to the customers on time, which will greatly improve the service level to the customers. 4) Fourthly, from the perspective of urban environment, an excellent distribution system is conducive to reducing the heavy traffic in the city, reducing noise pollution to the city and pollution by exhaust emissions. Segalou et a1. (2004) pointed out that emissions of nitrogen oxides and suspended particulates from cargo transport within cities accounted for 40% and 45% of total urban transport emissions. Therefore, through collaborative transportation and optimization of distribution routes, it is possible to reduce the number of trips, mileage, and empty-loading ratio of vehicles while meeting the needs of customers, and finally alleviate traffic congestion, noise pollution, and reducing emission quantity of the tail gas. 5) From the research perspective, the freight bus routing problem is a new periodic vehicle routing problem. This thesis considers this routing problem with three variants: the basic freight buses routing problem with delivery, the freight buses routing problem with both pickup and delivery, the freight buses routing problem with stochastic demands. The research results of this thesis enriches the literature of the vehicle routing problem.

Organization of this thesis

This thesis has 7 chapters, its structure is shown in Figure 1.1. The main contents and mutual relations of these chapters are outlined as follows: ...............................................................................................24 2.5

Introduction of the vehicle routing problem

The road transportation by vehicles is the most important part of many logistics systems, and the route optimization of vehicles has been a hot research topic for many scholars in the field of operations research and management science all over the world.

According to whether a single vehicle is or multiple vehicles are involved, the route optimization problem can be further classified into the Travelling Salesman Problem (TSP) and the Vehicle Routing Problem (VRP). The traveling salesman problem refers to finding an optimal tour for a single vehicle that starts from a depot, visits all customers, and finally returns to the depot to minimize the total running distance (total cost) of the vehicle. The vehicle routing problem refers to finding optimal tours for multiple vehicles, each of them starts from a depot, visits a subset of customers, and finally returns to the depot, with all customers visited by the vehicles, subject to various constraints such vehicle capacity constraints and time window constraints. The TSP was first proposed by Flood in 1956. Later, the VRP was introduced by Dantzig and Ramser in 1959 as an extension of the TSP and VRP, belonging to classic combinatorial optimization problems, have broad applications in real life, including the vehicle route problem in the express delivery industry, medical rescue, garbage clearance, manufacturing workshop logistics equipment scheduling , postal delivery problem etc.

For this reason, they have been attracting the research interest of many experts and scholars.

The research on vehicle routing problem involves management, logistics science, operations research, mathematics, computer application, graph theory, and other disciplines. A large variants of VRP have been proposed and studied in the literature, most of them have been proved to be NP-hard, which are very difficult to solve.

Scholars have proposed exact algorithms [START_REF] Christofides | Exact algorithms for the vehicle routing problem based on spanning tree and shortest path relaxations[END_REF][START_REF] Laporte | . An exact algorithm for the asymmetrical capacitated vehicle routing problem[END_REF]Lapone, 1992) and heuristic algorithms (Gendreau, 1994;[START_REF] Baker | A genetic algorithm for the vehicle routing problem.Computers[END_REF][START_REF] Prins | A simple and effective evolutionary algorithm for the vehicle routing problem.Computers& Operations Research[END_REF] to solve such problems. Since the exact algorithms can only handle small-size vehicle routing problem with about 50 customers, and the computation time of such algorithms increases exponentially with the increase of the problem size, they cannot be used to solve large-size vehicle routing problems. Therefore, most scholars turn their attention to heuristic algorithms, which aim to find a satisfactory solution to a VRP in an acceptable computation time.

In general, the vehicle routing problem covers many fields such as life, production, transportation, communication system, service system and so on. The scheduling object is not only vehicles, but also air flights and sea ships. Besides the minimum total cost, the goal of scheduling can also be the shortest total distance and time. In addition, what they have in common is to optimize the costs by choosing the right route. In order to describe conveniently and consistently, the transportation such as ships, airplanes, ambulances, garbage vehicles and transport vehicles are usually abstracted as Vehicle, the service objects of vehicles are abstracted as Customer, the service requirements of customers are abstracted as Demand, the vehicle dispatching center is abstracted as Distribution Centre(DC), the vehicle route is abstracted as Route, and the dispatch cost, fuel consumption, time and distance of vehicles are abstracted as Cost. The schematic diagram of vehicle routing problem is shown in Figure 2.1.

Fig. 2.1 An example of vehicle routing problem

Classification of vehicle routing problems

According to the existing research results, the vehicle routing problem can be classified as follows based on the degree of information determination and the constraint conditions.

(1)Vehicle routing problem with only delivery and with both pickup and delivery According to whether there are forward or reverse logistics operations or there are both, vehicle routing problems can be classified into vehicle routing problem with only delivery (or pickup) and the vehicle routing problem with both pickup and delivery(VRPPD). Vehicle routing problem with only delivery (or pickup) is also known as the Capacitated VRP (CVRP). The objective of this problem is to optimally assign all customers with delivery (or pickup) demand to vehicles and design an optimal route for each vehicle so that the total distance travelled by all vehicles is minimized without violating the capacity of each vehicle. A comprehensive review of this CVRP can be found in [START_REF] Bodin | Routing and scheduling of vehicles and crews: the state of the art[END_REF] and [START_REF] Eksioglu | The vehicle routing problem: A taxonomic review[END_REF]. Algorithms for solving CVRP are outlined in [START_REF] Laporte | Fifty Years of Vehicle Routing[END_REF], [START_REF] Chen | Iterated variable neighborhood descent algorithm for the capacitated vehicle routing problem[END_REF][START_REF] Drexl | Applications of the vehicle routing problem with trailers and transshipments[END_REF]. These algorithms include simulated annealing, tabu search, and genetic algorithms.

As an extension, [START_REF] Min | The multiple vehicle routing problem with simultaneous delivery and pick-up point[END_REF] studied the vehicle routing problem with both pickup and delivery, with an example of the problem which sends and returns books from a central library to 22 rural libraries. The author solved this problem by three-phase Chapter 2. Literature Review heuristics. Firstly, customers were clustered by the average linkage method. In the second phase, vehicles are assigned to these clusters and the Traveling Salesman Problem (TSP) algorithm was used to find routing solutions in the last phase. [START_REF] Salhi | A Cluster Insertion Heuristic for Single and Multiple Depot Vehicle Routing Problems with Backhauling[END_REF] designed a heuristic method using single-point insertion, two-point insertion, and cluster insertion to solve the VRPPD and extended it to the multi-depot problem with backhauls. Bent and Hentenryck (2006) apply Variable Neighbor-hood Search (VNS) to the vehicle routing problem with both pickup and delivery(VRPPD) and their computational results show promising performance of their algorithm, compared with the previous VRPPD metaheuristics. [START_REF] Ropke | An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[END_REF] design an ALNS algorithm which proved to be a effective meta-heuristic for the VRPPD, with results reported for up to 1000 customer nodes.

(2) Periodic and non-periodic vehicle routing problem

Vehicle routing problem can be divided into periodic problem and non-periodic problem(PVRP), according to whether the level of vehicle service time is periodic or not. The scheduling time of non-periodic problem is usually one day, and the scheduling time of a periodic problem can be a week, a month or a year. For periodic problems, the vehicle does not have to serve all customers every day, all the customer's demands within the cycle and the optimization goal is usually to minimize total cost at the whole cycle level. [START_REF] Yang | A multiperiod dynamic model of taxi services with endogenous service intensity[END_REF] studied the taxi scheduling problem, established a multiperiod dynamic model and used Frank-Wolfe algorithm to solve it. [START_REF] Francis | Modeling techniques for periodic vehicle routing problems[END_REF] studied the periodic problem with service selection. [START_REF] Gaudioso | A Heuristic for the Periodic Vehicle Routing Problem[END_REF] studied the periodic problem of minimizing the vehicles number and solved it by Hybrid heuristic algorithm. [START_REF] Mourgaya | Column generation based heuristic for tactical planning in multi-period vehicle routing[END_REF] studied the periodic problem with a scheduling period of 5 days and a customer scale of 50-80, and solved it by using a column-generated heuristic algorithm.

(3) Vehicle Routing Problem with Split Demand and Non-Split Demand According to whether the customer demand can be split, the vehicle routing problem can be divided into Vehicle Routing Problem with Split Demand (VRPSD) and Non-Split Demand. Modeling and solving of VRPSD are more difficult than the problem with non-split demand. [START_REF] Dror | Split delivery routing[END_REF] pointed out that VRPSD is a kind of Chapter 2. Literature Review VRP with relaxed constraints. When the demand of each customer in VRP except the parking lot can be completed by one vehicle, the number of vehicles and the total length of routes can be saved simultaneously. [START_REF] Sierksma | Routing helicopters for crew exchanges on offshore location[END_REF] pointed out that when the average demand was greater than 1/2 and less than 2/3, the VRPSD model can be used to solve the problem to the greatest extent. [START_REF] Frizzell | The split delivery vehicle scheduling problem with time windows and grid network distances[END_REF] used downward pruning heuristic algorithm to solve VRPSD, which took into account the factors of multi-time window, grid distance, multi-delay time and distribution time related to non-linear demand.

(4) Deterministic and stochastic vehicle routing problem

The vehicle routing problem can be divided into deterministic and stochastic problems based on whether the required information is predicted in advance. Because of the lack of information, the optimization objective of the stochastic problem is usually to minimize the expected total cost. According to the randomness of different information, the stochastic problem can be divided into the stochastic demands, the stochastic travel time and service time, and the stochastic customers.

A. Vehicle Routing Problem with Stochastic Demands (VRPSD)

In 1979, Golden et al. proposed a solution framework for Vehicle Routing Problem with Stochastic Demands (VRPSD),and assumed that each customer's demand was independent and obeyed the Poisson distribution. [START_REF] Stewart | Stochastic Vehicle routing: a comprehensive approach[END_REF] established several different mathematical models and proposed several heuristic algorithms to solve the VRPSD. Based on Clarke-Wright saving algorithm, [START_REF] Dror | Stochastic vehicle routing with modified savings algorithm[END_REF]proposed a forward modification saving algorithm to solve the VRPSD . [START_REF] Jaikumar | Tug fleet size problem for barge line operations: a polynomial algorithm[END_REF] (1996) turned their view to the automated material handling system, and considered the stochastic elements such as stochastic material demand and variable loading and unloading time, they established an stochastic modeling for automated material handling system. [START_REF] Teng | A comparative study of metaheuristics for vehicle routing problem with stochastic demands[END_REF] used simulated annealing algorithm, threshold Chapter 2. Literature Review acceptance method and Tabu search algorithm to solve the vehicle routing problem with stochastic demands, and the comparative analysis of the three algorithms shows that the Tabu search algorithm has the best performance. In terms of the computing time, the Tabu search algorithm takes less time than the simulated annealing algorithm.

Although the threshold acceptance method takes the least time, the quality of its solution is poor. [START_REF] Mirmohammadsadeghi | Memetic Heuristic Approach for Solving Truck and Trailer Routing Problems with Stochastic Demands and Time Windows[END_REF] studied the truck and trailer routing problem with stochastic demands and time windows, and solved the problem by using genetic algorithm. [START_REF] Kenyon | Stochastic vehicle Routing with Random Travel Times[END_REF] used the branch cutting-plane method to solve the vehicle routing problem with dynamic travel time. [START_REF] Bertsimas | A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane[END_REF] studied the vehicle routing problem with minimum expected total service time, proposed two queue priority processing strategies of "nearest neighbor" and "first come first service", and gave the lower bound of the problem. [START_REF] Fu | Improving paratransit scheduling by accounting for dynamic and stochastic variations in travel time[END_REF] studied the scheduling problem of dynamic stochastic travel time assisted passenger transport system. [START_REF] Gu | A dispatch model of emergency vehicles based on stochastic travel time.Proceedings of International Conference of Chinese Logistics and Transportation Professionals-Logistics: The Emerging Frontiers of Transportation and Development[END_REF] studied the multi-depot ambulance scheduling problem with stochastic travel time. The optimal solution of total delay time and total travel time was obtained by genetic algorithm. [START_REF] Zhang | A Stochastic Vehicle Routing Problem with Travel Time Uncertainly: Trade-Off between Cost and Customer Service[END_REF] prior route for all customers to be visited. The second stage was the improvement stage.

B Vehicle Routing Problem with Stochastic Travel Time and Service Time

Once the customers sent out the information that they needed services, the five neighborhood insertion mechanism was used to insert the client into the a priori route by minimizing the expected cost, and the post-optimization route was obtained. [START_REF] Thomas | Waiting strategies for anticipating service requests from known customer locations[END_REF] studied the dynamic vehicle routing problem with service requests, formulated waiting strategies based on maximizing the number of expected service customers, and proposed a heuristic method to solve the problem.

(5) Vehicle routing problem without time window and with time window

According to whether the customer service has specific time window constraints, or whether the vehicle has time limit to start and return, the vehicle routing problem can be divided into the problem without time window and with time window(VRPTW).

VRPTW can be further divided into hard time window problem and soft time window problem, time-varying problem and non-time-varying problem, single time window problem and multi-time window problem. For the time-window problems, [START_REF] Kallehauge | Formulations and exact algorithms for the vehicle routing problem with time windows[END_REF] and [START_REF] Tan | Heuristic methods for vehicle routing problem with time windows[END_REF] summarized the exact algorithms and heuristic algorithms respectively. [START_REF] Kim | Waste collection vehicle routing problem with time windows[END_REF]

Main algorithms for solving vehicle routing problems

The current algorithms for vehicle routing problems can be divided into accurate algorithm and heuristic algorithm. Because of the NP-Hard property of VPR, the accurate algorithm can only solve the small-scale vehicle routing problem. For the vehicle routing problem with more than 50 customer points, the accurate algorithm cannot get the optimal solution of the problem. Therefore, the heuristic algorithm, which uses medium computing time to obtain the approximate or satisfactory solutions of VPR, has become the focus of scholars' research. In the following, only the heuristic algorithm (including Simple Heuristics Algorithm and Metaheuristic Algorithm) for solving the vehicle routing problem is reviewed.

Simple heuristic algorithms

Saving heuristic

Saving Heuristic was proposed by Clarke and Wright in 1964 to solve the VRP with an unfixed number of vehicles. The Saving Heuristic is a successive approximation algorithm for vehicle routing based on the saving criterion.

The principle of the Saving Heuristic is simple and easy to implement. At present, it has become an initial solution algorithm for many heuristic algorithms to solve VRP.

Because of the fast operation speed of the Saving Heuristic, the approximate optimal solution to the problem can be obtained efficiently in the small-scale distribution optimization, but the optimization effect is not ideal when the number of customer increases.

Nearest neighbor method

The nearest neighbor method was first proposed by [START_REF] Rosenkrantz | An analysis of several heuristics for the traveling salesman problem[END_REF]. The algorithm takes the distribution center as the starting point, searches for the nearest and unaccounted node to the distribution center as the next node, then searches for the neighboring and unaccounted nodes, repeats the above steps without exceeding the capacity limit, finishes the line after reaching the capacity limit, and continues to search for other new routes until all the nodes have been visited. This algorithm is simple to operate and can get the initial solution quickly, but it is easy to produce premature convergence and fall into local optimum.

Chapter 2. Literature Review

Insertion method

The insertion method is proposed by [START_REF] Mole | A sequential route-building algorithm employing a generalized savings criterion[END_REF] to solve the VRP .

The insertion method combines the ideas of the nearest neighbor method and the saving heuristic, and selects the most suitable unallocated nodes to insert. That is to build a distribution route until a new route is added when there is no viable insertion node. The solution obtained by the insertion method is better than the solution obtained by the nearest neighbor method, but the calculation amount is also larger.

Sweep algorithm

The sweep algorithm was proposed by [START_REF] Gillett | A Heuristic Algorithm for the Vehicle-Dispatch Problem[END_REF] The basic idea of the algorithm is to assume that the vehicle route is located on a geometric plane, and the distribution center is used as the coordinate origin to establish a polar coordinate system. Firstly, the polar coordinates of the customer points to be visited are calculated and sorted according to the angle. Then, on the premise of the feasibility condition, the customers are added to the distribution route one by one in the clockwise or counterclockwise direction from the node with the smallest angle, and the distribution route is terminated when the constraint condition is not satisfied. Repeat the process and generate the new distribution routes until all customers are added.

Metaheuristic algorithms

As an improved heauristic algorithm, metaheuristic algorithm has been widely used with its powerful functions in combinatorial optimization problems.

Tabu search algorithm

The idea of Tabu Search (TS) was first proposed by Fred Glover in 1986. The Tabu Search algorithm is a global stepwise optimization algorithm, which is a simulation of human intelligence process. The TS algorithm avoids the roundabout search by introducing a flexible storage structure-the tabu table and setting the corresponding tabu criteria, and uses the amnesty criteria to absolve some of the tabu good conditions, thus ensuring effective exploration of diversity to finally achieve global optimization.

In 1991, Gendreau et al. first applied this method to solving the VRP. In 1993, E.Taillard used Tabu Search as an iterative search algorithm to solve the sub-problems.

The TS algorithm has a strong dependence on the initial solution. Therefore, many scholars have adopted different initialization methods, for example [START_REF] Garcia | A parallel implementation of the tabu search heuristic for vehicle routing problems with time window constraints[END_REF] using Solomon's insertion heuristic algorithm to construct the initial solution, [START_REF] Cordeau | A guide to vehicle routing heuristics[END_REF] adopting an improved scanning method to generate the initial solution, Brandao using the lower bound algorithm and the K-tree algorithm to generate the initial solution, [START_REF] Lau | Vehicle routing problem with time windows and a limited number of vehicles[END_REF] creating a candidate list and generating an initial solution by transposing the unvisited customers in the list. [START_REF] Rochat | Probabilistic diversification and intensification in local search for vehicle routing[END_REF] proposed a method of adaptive memory, which first saves the excellent solutions found in the search process, and then through the combination of these solutions, generates an initialization new solution. The TS algorithm has been easily applied to other extended models of vehicle routing problems since it does not need to set special encoding rules and operators.

Simulated annealing algorithm

Simulated Annealing (SA) is a kind of algorithm for solving combinatorial optimization problems proposed by Kirkpatrick et al. in 1983, inspired by the principle of solid-state physics annealing and based on Metropolis criterion. The simulate anneal arithmetic is essentially a local search algorithm, but in order to avoid the algorithm falling into local optimum, it introduces a new mechanism, that is, to accept the poor solutions in the neighborhood in the way of probability so as to enhance the diversity of the algorithm. Bent et al.(2004 ) proposed a two-stage hybrid optimization method. In the first stage, the SA algorithm is used to minimize the number of vehicles. In the second stage, the Large Neighborhood Search algorithm is used to optimize the customer's ordering.

The simulate anneal arithmetic is suitable for large-scale VRP problems. In theory, SA can obtain the global optimal solution, but in practical applications, due to the limitation of calculation time, only an approximate optimal solution can be given.

Genetic algorithm

Genetic Algorithm is a kind of random search method which is derived from the evolutionary law of biology (survival of the fittest Genetic mechanism). It was first proposed by American professor J.Holland in 1975, and its main feature is to operate directly on structural objects. The operators include selection operators, crossover operators, and mutation operators. [START_REF] Thangiah | Gideon: A genetic algorithm system for vehicle routing with time windows[END_REF]first applied genetic algorithms to solving the vehicle route problem with time window. [START_REF] Gehring | Parallelization of a two-phase metaheuristic for routing problems with time windows[END_REF]studied the application of two evolutionary strategies in vehicle routing problems. In the use of genetic algorithm to solve VRP problems, many scholars have improved the traditional evolutionary operations. Jean-Yves [START_REF] Potvin | The Vehicle Routing Problem with Time Windows-Part II: Genetic Search[END_REF] proposed two special crossover operators: sequence-based crossover and route-based crossover. The mutation operator is used to reduce the number of lines. The selection strategy uses the so-called Linear Ranking Scheme, that is, the probability of selection of each individual is related to its ranking, and the ranking is determined based on the size and fitness of the swarm. [START_REF] Berger | A hybrid genetic algorithm for the vehicle routing problem with time windows[END_REF] first used the random insertion algorithm to generate the initial solution, and then used the improved Large Neighborhood Search (LNS) and improved Solomon insertion algorithm combined with genetic operations to redistribute customers to reduce the route. When [START_REF] Bouthillier | A cooperative parallel meta-heuristic for the vehicle routing problem with time windows[END_REF] And in the context of complex optimization, many different instantiations of memetic algorithms have been reported across a wide range of application domains, in general, Chapter 2. Literature Review converging to high-quality solutions more efficiently than their conventional evolutionary counterparts [START_REF] Samanlioglu | A memetic random-key genetic algorithm for a symmetric multi-objective traveling salesman problem[END_REF][START_REF] Mafarja | Investigating memetic algorithm in solving rough set attribute reduction[END_REF]. So far, MA has been used with great success to solve various vehicle routing problems, including various single period VRPs (capacitated VRP, VRP with time windows, pickup and delivery problem) and the PVRP.

Ant colony optimization algorithm

In 1991, Dorigo was inspired by the foraging behavior of ants in nature, and simulated the path finding behavior of ants to put forward an ant colony optimization algorithm. The basic principle of the ant colony optimization algorithm is that ants will transmit information through pheromone to guide their movement direction in the process of searching for food. The colony behavior of a large number of ants will show an information positive feedback phenomenon, that is, the more ants passing on a route, the more likely the subsequent ants will choose the route. [START_REF] Bullnheimer | Applying the ant system to the vehicle routing problem[END_REF] first applied the ant colony algorithm to solving the vehicle routing problem, after using the ACO, the 2-opt method is used to optimize the route, and in the research the optimal solution of the problem is obtained. [START_REF] Reimann | A savings based ant system for the vehicle routing problem[END_REF] introduced the classical saving algorithm into the ant system and constructed the Savings-based Ant System (SbAS). Unlike the ant algorithm, its decision rules include not only the pheromone of ant algorithm, but also embeds the saving value therein. [START_REF] Reimann | A savings based ant system for the vehicle routing problem[END_REF] extended the SbAS algorithm based on the literature, that is, using the scanning method to decompose the large-scale VRP problem, and then using the SbAS algorithm to solve each sub-problem. The improved SbAS algorithm can effectively improve the calculation speed.

At present, although the ant colony algorithm has made great progress in solving the VRP problem, the solution speed and the quality of the obtained solution are still not ideal when solving the large-scale combinatorial optimization problems.

Particle swarm optimization

Particle Swarm Optimization (PSO) is an evolutionary computational technique developed by Kennedy and Eberhart in 1995. The particle swarm algorithm expresses each possible solution as a particle in the swarm, and each particle has its own velocity and position vector, and an adaptive value determined by the objective function.

At present, the application of particle swarm optimization in vehicle routing problems has not been extensively studied. Wu Bin (2008) proposed a particle swarm optimization method that uses integer encoding and real number encoding to solve the VRP problem in his doctoral thesis. In integer encoding, based on the number of exchanges, the velocity of the particle is redefined, and a velocity calculation method is used for integer encoding. The influence of each parameter in the particle swarm algorithm on the result is discussed in the thesis. Chen et al.(2006) studied the application of particle swarm optimization algorithm with mutation operator in vehicle routing problem, that is, in the basic framework of conventional particle swarm optimization algorithm, the random variation factor is added to improve the ability of the algorithm to jump out of local convergence by random mutation of g best . Chen et al.(2006) proposed a method to solve the vehicle routing problem by combining Discrete Particle Swarm Optimization (DPSO) and the simulate anneal algorithm.

Adaptive Large Neighborhood Search Algorithm

The precursor of the Adaptive Large Neighborhood Search Algorithm (ALNS) is Large Neighborhood Search (LNS), introduced by Shaw(1998) for the capacitated vehicle routing problem (CVRP). LNS begins with an initial solution and improves the objective value gradually, by applying one destroy and one repair operator at each iteration. The destroy operator is a randomized heuristic removing a small subset of customers. The repair operator reinserts these customers optimally, using constraint programming and branch-and-bound, see Bent et Hentenryck (2006) for the VRPTW.

The destroy and repair operators are also called ruin and recreate operators, or removal and insertion operators.

The application of a destroy/repair pair can be viewed as a move that implicitly defines a very large neighborhood. However, only one move is randomly selected at each iteration instead of exploring the neighborhood completely. LNS is conceptually simple but has some known drawbacks. The search is a bit blind because the destroy/repair moves sample a very small fraction of the large neighborhood. This can be compensated by more iterations but, added to the exact method used to reinsert customers, the metaheuristic becomes time-consuming.

Adaptive Large Neighborhood Search (ALNS) is an extension of Large Neighborhood Search and was proposed by [START_REF] Ropke | An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[END_REF] . The schema of ALNS is shown in Figure 2.2 in the form of a picture.

Fig. 2.2 The schema of ALNS

The ALNS involves several destroy and repair operators, which are all heuristics to achieve a time-saving purpose. At each iteration, a pair of operators is randomly chosen to make a move and statistics are computed to favor the most efficient pairs. The method is adaptive since the most frequent pairs may change during the search.

Naturally, different problem instances and even different solutions to the same problem are handled by different destroy and repair heuristics with varying success. It may often be difficult to guess which heuristics will be the most advantageous.

Therefore, ALNS enables the user to select as many heuristics as he wants. The algorithm will then assign a weight to each heuristic which reflects its success. In the absence of other possibilities, it assumes the past success as the best indicator for future success. During the runtime, these weights are adjusted periodically. An update period consists of 𝑃 𝑢 iterations. The selection of a heuristic in each iteration is then based on these weights. Let D = {𝑑 𝑖 |𝑖= 1, … , k } be the set of k destroy heuristics and R ={𝑟 𝑖 |𝑖= 1, … , l } be the set of l repair heuristics. The initially equal weights of the heuristics are denoted by w(𝑟 𝑖 ) and w(𝑑 𝑖 ), so that the probabilities to select a heuristic are

P(𝑟 𝑖 ) = 𝑤(𝑟 𝑖 ) ∑ 𝑤(𝑟 𝑗 ) 𝑘 𝑗=1 ,P(𝑑 𝑖 ) = 𝑤(𝑑 𝑖 ) ∑ 𝑤(𝑑 𝑗 ) 𝑙 𝑗=1 respectively (2.1)
Compared to many local search heuristics that only apply very small changes to a solution, ALNS works with a larger search space, the so-called neighborhood of the current solution. Within one iteration, ALNS can modify up to 30-40% of a solution.

This characteristic is especially useful with tightly constrained problems like the VRP.

The ALNS has been successfully applied to the VRPPD (Ropke & Pisinger,2006) and later to various rich vehicle routing problems (Pisinger & Ropke,2007).

Collaborative logistics

Collaborative logistics has received increasing attention in past years, often driven by the large potential in cost reduction, reduction of uncertainty, and environmental concerns [START_REF] Verdonck | Collaborative logistics from the perspective of road transportation companies[END_REF][START_REF] Du | Liner shipping fleet deployment with sustainable collaborative transportation[END_REF]. There are many benefits to be achieved through collaboration, the main benefits of which are lower cost and higher fulfillment rate. On the social side, collaboration usually decreases the traveled distance by carriers, which implies fewer emissions. In that way, collaboration can promote green logistics and reduces negative impacts on the environment. [START_REF] Cleophas | Collaborative urban transportation: Recent advances in theory and practice[END_REF] Examples of horizontal cooperation in logistics include group purchasing, use of a common inventory location to share fixed costs, collaborative transportation [START_REF] Quintero-Araujo | Using horizontal cooperation concepts in integrated routing and facility-location decisions[END_REF], and production lines sharing. Horizontal collaboration in logistics has been studied in the maritime transport [START_REF] Sheppard | Ocean shipping alliances: the wave of the future[END_REF], disaster relief [START_REF] Schulz | Horizontal cooperation in disaster relief logistics: benefits and impediments[END_REF][START_REF] Garrido | A stochastic programming approach for floods emergency logistics[END_REF], and airline fields [START_REF] Weng | Flow merging and hub route optimization in colla borative transportation[END_REF].

The literature is rich in vertical cooperation [START_REF] Huang | Coordination in a retailer-dominated supply chain with a risk-averse manufacturer under marketing dependency[END_REF][START_REF] Liu | Ordering and returns handling decisions and coordination in a supply chain with demand uncertainty[END_REF], but the environment is quite different. A recurrent example of vertical collaboration can be found in the Collaborative Planning Forecasting and Replenishment, where manufacturers and retailers share information and make common predictions to improve demand visibility, thereby increasing the efficiency of the supply chain. We can anticipate that some practical issues in vertical collaboration apply also to horizontal collaboration. We recommend readers to [START_REF] Kanda | Supply chain coordination: perspectives, empirical studies and research directions[END_REF] for a complete review of supply chain collaboration, including some practical issues. [START_REF] Kopfer | Approaches for modelling and solving the integrated transportation and forwarding problem[END_REF] provide an overview and a comparison of existing methods for modeling and solving the integrated transportation and forwarding problem. And this is an extension of the traditional path and scheduling issues for freight forwarders provided by 3rd and 4th party logistics. This study summarizes the reasons for the existence of the gap between theory and practice.

D'Amours et Rönnqvist (2010) present a survey of previous contributions in the field of collaborative logistics. Firstly, they portray opportunities in collaborative transportation planning. Then they discuss key issues in forming alliances, such as sharing resources and profits, as well as the issues related to information protection and decisions technologies. Finally, they raise some question and describe the prospects of future research.

Collaborative urban transportation

Increasing urbanization has turned transporting freight from, to, and within urban areas into a major challenge. Freight transportation represents a lifeline of urban retail and industry, but it has a serious negative impacts on the quality of living in urban areas in terms of congestion, emissions and space consumption. Urban logistics initiatives have long suggested the need for collaborative and environmentally friendly urban transportation that could alleviate the negative impacts of urban transportation, but these face organizational and technological challenges of cooperation. Given technological advancements and innovative business models, concepts of collaborative urban transportation could contribute to a future paradigm of more sustainable and customer-friendly urban transportation. (Basso et.al, 2019) There are two main types of collaborative transport: vertical and horizontal. For vertical collaboration, transport is often organized according to modes and service operators. For instance, the first leg in the city can be carried out by conventional trucks, while the last mile of to the recipient can be operated by environment-friendly city freighters or freight bikes. In horizontal collaboration, multiple providers work together in the same section of the transport chain, potentially sharing orders and infrastructure.

In most cases, urban transport utilizes standard trucks or light goods vehicles up to 3.5 tons, respectively. [START_REF] Browne | Light goods vehicles in urban areas[END_REF] As described in Chapter 2, many large cities are currently exploring new solutions for collaborative logistics and collaborative transportation. In this chapter, we will propose the concept of a freight bus system in urban logistics , analyze its advantages, and address some important issues for the implementation of such a system in an urban area including the infrastructure and the operation management.

Proposal of freight bus in urban logistics

Key issues in our urban logistics

After analyzing a large number of literature and industry observations, we can identify some key issues in urban logistics as follows:

First, the infrastructure of urban logistics transportation needs to be upgraded and transformed. The development of socialized production in modern time is reflected in the urban logistics field and is manifested in large-in and large-out as well as fast-in and fast-out of the goods, which requires us to upgrade and transform the old urban logistics infrastructure; Second, the quality and efficiency of the "last mile" service in urban logistics needs to be improved. With the investment from the government and enterprises in urban logistics, the logistics distribution has basically reached a certain level of service in truck-road transportation but due to the features of multiple demand points and complex traffic flow of the "last mile distribution", at present, the distribution of "last mile" cannot meet the customer's service needs. Third, Various logistics companies still lack cooperation. Due to the lack of effective cooperation and management, repeated transportation and empty return in the transportation process still exist. The waste of transportation capacity, on the one hand, increases logistics costs and, on the other hand, intensifies the urban problems such as urban congestion, environmental pollution and noise pollution and so on. Fourth, the urban logistics needs to improve its own mechanization and informatization level, and with the development of e-commerce, the demand for urban logistics is featured by "more variety, small batch, multiple batches, short cycle", which requires the urban logistics to be strengthened in mechanization and information level to adapt to new demands. Fifth, The government needs to make unified planning and management for the healthy development of urban logistics. Currently, because of the huge market of urban logistics, some large logistics enterprises blindly expand and repeatedly construct the logistics network and logistics facilities and these homogeneity competitions in return cause a certain amount of social waste. The government needs to plan and manage urban logistics from the macro perspective.

In response to these problems in urban logistics, we put forward the freight bus distribution system. The freight bus system will focus on solving the problems such as "last mile", coordinated distribution, and unified planning. First of all, the freight bus is running in the city center, which is a new distribution scheme focusing on solving the "last kilometer' problem of the city. Secondly, the freight bus will replace the original city vehicles which are operated separately in the city to realize cooperative transportation, which will effectively improve the phenomenon of repeated transportation and empty return. Thirdly, the freight bus system will be unified construction and unified management and operation, which will greatly improve the situation of repeated construction and malicious competition. In addition, the construction of freight bus system will contribute to the specific implementation of information and mechanization of urban logistics service upgrading.

Three-tiered distribution system

The three-tiered distribution system evolved from the two-tiered system [START_REF] Crainic | Advanced freight transportation systems for congested urban areas[END_REF]. The first tier is between city distribution centers (CDCs) and satellite platforms. The second tier is between satellite platforms and depots. The third tier is between depots and customers. These three tiers have different types of vehicles employed: urban vehicles, city freighters and electro-tricycles. The following two figures show their differences. In the two-tiered distribution system, there are usually a lot of satellites in the center of a city. At first, the urban vehicles deliver the goods from a CDC to multiple satellites.

Then the electro-tricycles deliver the goods from satellites to customers. The follow table gives the vehicles of different tiers: We can see by adopting the three-tiered distribution system, the running distance of tricycles can be greatly reduced, and it will greatly reduce the labor costs. However, accompanied with the three-tiered distribution system, we can see that a lot of city freighters were born and circulate in the city center. The market opportunity of urban logistics has been creating more and more city freighters in the city center. As a result, the traffic congestion in the city center becomes more and more severe. The traffic control for city freighters, on the one hand, is difficult to implement, and on the other hand cannot improve the efficiency of urban logistics significantly. In order to solve these problems, we put forward the concept of freight bus.

Introduction of freight bus in urban logistics

With the increase of freight distribution in urban transportation, and driven by the market demand, more private city freighters were born in the centers of cities, which makes their traffic more congested and the air pollution more severe in metropolitan areas. Motivated by joint distribution, in this thesis, we put forward the concept of the freight bus, which is a new public transportation means for urban logistics that can replace city freighters belonging to different private third-party logistics companies in the center of a city [START_REF] Dai | Mathematical model and solution approach for collaborative logistics in less than truckload (LTL) transportation[END_REF]). In the following two figures, city freighters are compared with freight buses in urban distribution systems. We can see in As a public service for third-party logistics companies and customers, the use of freight buses can achieve joint distribution. One important feature of freight buses is that they are standardized vehicles and have fixed routes and time schedules. Like passenger buses, a fixed vehicle route for each freight bus may not be the most economical in terms of cost, but with the fixed routes and schedules, freight buses can provide a stable and accurate service, and both shippers and customers can flexibly arrange their order delivery times. Each depot in such distribution system is a freight bus station, which may be a smart cabinet (depot) for temporary storage of goods. According to the schedules, customers can pick up their ordered products by self-service at the freight bus stations (depots), or ask the last-mile delivery men to deliver the goods from a freight bus station to their homes [START_REF] Taniguchi | An Evaluation Methodology for Urban logistics[END_REF]. The following figure 3.5 illustrates freight buses lines, where each freight bus station is visited and served by a freight bus line periodically. In each run (period), each freight bus starts from the distribution center, distributes goods to multiple depots, and finally returns back to the distribution center, according to a predefined route and time schedule. Moreover, as a public transportation means, freight buses can also enjoy the policy of bus priority and the use of special lanes reserved for buses, which can improve the timeliness and accuracy of logistics services.

Fig.3.5 An example of freight buses lines

In a more precise way, the freight bus can be defined as follows: freight bus is a public vehicle travelling in a city, which provides services for urban logistics. Like a passenger bus, each freight bus has a fixed route and time schedule and can use special lanes reserved for buses.

Advantage of freight bus system

Compared with city freighters, we can expect that freight buses have some advantages because of their utilization shared by all suppliers and customers. Firstly, the use of freight buses can realize joint distribution of multiple third-party logistics companies, and can thus save urban logistics costs and reduce the air pollution;

Secondly, because of having a regular schedule, the use of freight buses can improve the timeliness and accuracy of logistics services; Thirdly, replacing private city freighters by freight buses can facilitate traffic control in a city and reduce the traffic congestion.

In addition, the use of freight buses can improve the utilization rates of special lanes reserved for buses. Just like buses, with the increase of freight transportation demand and the increase of city freighters in the city center, we believe that freight buses will certainly play an important role in modern urban distribution.

We have quantitatively compared an urban distribution system with freight buses with a system with city freighters in terms of logistics costs under some assumptions on the operations of the two systems (see Chapter 5, section 5.4.4). From our preliminary experimental results, we find that if we use the proposed freight bus system, the cost saving in percentage compared with the system without freight bus is ranged from 17.6% to 35.3% with the average cost saving 25.1%. The experimental results show that the system with freight bus can significantly reduce transportation costs compared with the system without freight bus.

Implementation issues of the freight bus system

In this section, we will discuss how to build and operate a freight bus system in terms of infrastructure and operation management:

Infrastructure of freight bus system

The proposed system can be technologically developed based on existing logistic devices to provide public logistics transportation service. A public freight bus system mainly consists of four components: user interface, freight bus stations, freight bus vehicles, communication devices. The structure of a public transit-based logistics transportation system is displayed in Figure 3.6, and each component is explained as follows. (Shen,Qiu,Li and Feng,2015). With this interface, customers can know the delivery status of their goods, and a pickup reminder will be sent from the system server to a customer when the goods are unloaded at a targeted bus station.

Freight bus stations

The location of freight bus stations should be as close as possible to passenger bus stations, so that passengers can pick up the goods when they commute to and from work (school). According to the daily volume of freight to deliver/pickup and the existing logistics equipment, the sizes and the required equipment of different freight bus

Chapter 3. Freight Bus in Urban Logistics stations may be different, but each freight bus station should include the following three things: freight bus station sign, dedicated parking area, and good storage site.

The freight bus station sign can help users and the freight bus driver determine the location to deliver/pickup goods. On the other hand, the freight bus station sign also shows the timetable for the access of a freight bus, so that the users can arrange their goods delivery/pickup plans.

Because of a fixed access schedule, freight bus vehicles should have a fixed parking area. In addition, freight buses can also share existing passenger bus lanes to ensure the punctuality of goods delivery/pickup.

According to the volume of goods to deliver/pickup, the goods storage site of a freight bus station can be a special shop (newsstand) or a smart cabinet. For example, in some cities in China, where e-commerce is relatively developed, special smart cabinets are installed in major residential areas. This smart cabinet allows users to make self-service delivery or pickup.

Freight buses

As a new public transportation means for urban logistics, freight buses should be specially designed and manufactured. Firstly, since freight buses are to be operated in urban centers, the energy used by each freight bus should be green and clean, such as natural gas or pure electricity; Secondly, in order to facilitate the rapid loading and unloading of goods, a freight bus should have automatic loading/unloading devices for goods to facilitate the movement of goods up and down. Thirdly, in order to improve the efficiency of delivery and pickup, the space design inside a freight bus should maximize the loading capacity of goods. Fourthly, in order to provide customers with timely delivery/pickup information of goods, each freight bus should be equipped with a GPS system. Finally, the interior of each freight bus should be equipped with an appropriate equipment for safety, fire protection and operation in special condition (e.g. low temperature, etc.).

Communication device

A communication device is used as a link between two components of a freight bus system and to transmit real-time instructions and status updates. Generally, each

Chapter 3. Freight Bus in Urban Logistics component of the system is connected through an existing internet infrastructure. Each freight bus relies on a wireless communication network to receive instructions and send its position and operational data back to the system server which is connected to customers logistics companies, and goods suppliers.

Operation management of freight bus system 1 Information Sharing

As the upgrade and optimization of a current urban distribution system, it is necessary for a freight bus distribution system to strengthen its own information collection and sharing. The logistics participants such as customers, manufacturers, third-party logistics companies, couriers shall achieve information sharing and all participants in logistics activities shall be able to get access to the real-time status information of goods in delivery.

Rules and Regulations

As a public transportation means, the operation of freight buses shall enjoy the policy of " public transportation first". The freight buses shall have the priority in using urban roads, and should able to use public transportation special lines if the road conditions of the lines are allowed. In addition, the safety of goods in each freight bus shall be protected by special rules and regulations.

Cost share and revenue management strategy

The freight bus system involves all participants of urban logistics, including thirdparty logistics companies, goods suppliers, and customers, so it is necessary to adopt a reasonable revenue management strategy by fairly sharing costs among these participants.

Standardization

The construction of a freight bus system shall promote the standardization of urban logistics system, including the standardization of freight bus vehicles by considering environmental protection, safety and other aspects, the standardization of logistics distribution schedule, and the standardization of goods size and packaging and so on.

Training of professional personnel

As a new urban logistics system, the efficient operation of the freight bus system needs a group of professional logistics practitioners, so it is necessary to have a

professional training for all operators and service providers of the system to ensure its efficient and safe operation.

Introduction

After putting forward the concept of freight buses, we need to address the issue "how to operate them efficiently." One important problem relevant to the operation of freight buses is their route planning, which is related to period vehicle routing problem.

In the standard periodic vehicle routing problem (PVRP), each customer is required to be visited on one or multiple days within a planning period of several days, and there are a set of feasible visit options (days) for each customer. For example, a customer is required to be visited twice in the planning period of one week and a feasible visit option for the customer is Monday and Wednesday. After assigning a feasible visit to each customer, a VRP is solved for each day in the planning period. The objective of the problem is to minimize the total distance traveled over the planning period [START_REF] Campbell | Forty Years of Periodic Vehicle Routing[END_REF]. However, our route planning problem of freight buses has the following two new features. Firstly, as one type of public transportation means, each freight bus has a fixed vehicle route, and all depots or customers are visited by the freight buses with the same number of times per day. Secondly, because of the capacity limitation of a freight bus,it is possible that the demand of a depot in a period is only partially met in this period. In this case, the unmet demand of the period can only be met in later periods and with a late delivery penalty. so our route planning problem of freight buses is a new variant of periodic vehicle routing problem. To the best of our knowledge, buses dedicated to the transportation of freight were rarely addressed in the literature and the freight bus routing problem considered in this thesis was never studied by other researchers.

In this chapter, we will study the basic route planning of freight buses with only delivery. Each freight bus is assumed to be operated periodically with a fixed route. We consider an urban distribution system where freight buses deliver goods (customer orders) from an urban distribution center to a set of depots.

In order to solve the problem, In this chapter, we first formulate our basic route planning of freight buses with only delivery as a Mixed-Integer Linear Programming

Problem description and mathematical model

Problem description

In the model, the freight buses deliver goods from a Distribution Center to a set of depots. For simplicity, we don't consider the interactions of the freight buses with the electro-tricycles which perform last-mile deliveries from depots to customers. We divide the planning time horizon (e.g. one day) of freight bus operations into M periods (M > 1). As the first study of freight bus routing problem in this thesis, we assume the demand at each depot in each period is known. This demand may be forecasted in advance every day or may be approximated by the average of historical demands of the depot in the same period and on the same day in each week during one year, one quarter, or one month. In addition, we assume each freight bus has a fixed route in the time horizon, and every depot must be served by one freight bus in each period. The total delivery demand of each depot must be met at the end of the time horizon, but it is possible that the demand of a depot in a period is only partially met in this period because of the capacity limitation of a freight bus. In this case, the unmet demand of the period will be met in later periods but with a late delivery penalty linearly depending on the quantity of the late delivery and the number of periods delayed. Because of the late delivery penalty, all demands must be met as early as possible.

The main parameters of the model are defined as follows:

• o The distribution center where each freight bus leaves from and returns to.

• 𝑉 Set of freight buses.

• G Set of depots.

•

𝑈

The capacity of each freight bus.

• 𝐶 𝑖𝑗 The operating cost for a freight bus travelling from node i to node j (i, jϵ{s} ∪ 𝐺).

•

M

The number of time periods we consider in the route planning problem.

• 𝑑 𝑖 (k) The delivery demand of depot i during the k-th period, 𝑖 ∈ G, 𝑘 ∈ {1,2 … 𝑀}.

• P Penalty coefficient (per period and per unit of demand) for the late delivery.

We assume that the Distribution Center o serves all depots G in the distribution system considered. The distance between node i and node j is denoted by 𝐷 𝑖𝑗 . Each

Freight bus loads the goods at the Distribution Center o, delivers them to a subset of depots, and finally returns to the distribution center. The operating cost of a freight bus from node i to node j is calculated as 𝐶 𝑖𝑗 = 𝐶 * 𝐷 𝑖𝑗 , where C is the unit distance operating cost of each freight bus. There are F (F is an integer) freight buses operated for the Distribution Center o, and the capacity of each freight bus is U.

In each period, each freight bus leaves from the Distribution Center o, visits its served depots and returns to the Distribution Center. What's more, every period, all the goods must be unloaded from the freight bus before it returns to the Distribution Center. It is assumed that the demand 𝑑 𝑖 (𝑘) of each depot i in each period 𝑘 ∈ {1,2 … 𝑀} is known. In each period, the delivery of freight bus v at each depot i can be the demand of that period plus the demand (the partial demand) of earlier periods but cannot be the demand of a later period.

We need to plan the vehicle route for each freight bus v, and the delivery quantity of each freight bus at each depot in each period. Our objective is to minimize the operating costs of all the freight buses plus the late delivery penalty costs in the M periods.

Mathematical model

As we can see from the Problem Description, there are three important characteristics for the basic route planning of freight buses: Firstly, each freight bus has a fixed route in the time horizon, and each depot must be served by one freight bus in each period.

Secondly, the demand of a depot in each period can be split into the demand delivered on-time in this period and the demand delivered in later periods because of the capacity limitation of a freight bus involved. Thirdly, because of the late delivery penalty, all demands must be met as early as possible.

Combining these characteristics, in this subsection, we propose a mathematic model for this basic route planning of freight buses. With this mathematic model, we can calculate the operating costs of freight buses and the penalty cost for the late deliveries in the planning horizon. At the same time, we can also get the optimal routes of freight buses by solving the model.

The detailed mathematical model for the route planning of freight buses is given as follows:

Decision Variables • x 𝑖𝑗 v
A binary variable which is equal to 1 if the freight bus v 𝜖𝑉 goes from node i to j (i, j𝜖{𝑜} ∪ 𝐺), and 0 otherwise.

• y 𝑖 v

A binary variable which is equal to 1 if and only if the depot i 𝜖𝐺 is served by the freighter bus v 𝜖𝑉,and 0 otherwise.

• d 𝑖 v (k)
The quantity unloaded from freighter bus v 𝜖𝑉 at the depot i 𝜖𝐺 in its k-th visit k∈ {1,2 … 𝑀}, and 0 otherwise.

• 𝑄 𝑖 𝑣 (k)
The load of the freighter bus v 𝜖𝑉 when it just arrives at node i 𝜖{𝑜} ∪ 𝐺 during its k-th visit, k∈ {1,2 … 𝑀}.

Objective Function

The objective is to minimize the sum of the costs which include the operating costs of the freight buses and the penalty costs for the late deliveries in the planning time horizon of M periods.

Min

Obj = 𝑀 * ∑ ∑ ∑ 𝑐 𝑖𝑗 𝑥 𝑖𝑗 𝑣 𝑣∈𝑉 𝑗∈{0}∪𝐺 𝑖∈{𝑜}∪𝐺 + P* ∑ ∑ (∑ 𝑑 𝑖 (𝑘) 𝑛 𝑘=1 -∑ ∑ 𝑑 𝑖 𝑣 (𝑘) 𝑛 𝑘=1 𝑣𝜖𝑉 𝑀 𝑛=1 𝑖∈𝐺 ) Subject to ∑ x 𝑜𝑗 v 𝑗∈G = ∑ x 𝑗𝑜 v j∈G ∀v ∈ 𝑉 (4.1) ∑ x 𝑖𝑗 v 𝑖∈{o}∪G = ∑ x 𝑗𝑖 v 𝑖∈{0}∪G ∀𝑗 ∈ 𝐺, ∀v ∈ 𝑉 (4.2) ∑ x 𝑖𝑗 v 𝑖∈{o}∪G = y 𝑗 v ∀𝑗 ∈ 𝐺, ∀v ∈ 𝑉 (4.3) ∑ y 𝑗 v v∈V = 1 ∀𝑗 ∈ 𝐺 (4.4) 𝑄 𝑗 𝑣 (𝑘)>=𝑄 𝑖 𝑣 (𝑘)+𝑑 𝑗 𝑣 (𝑘)-𝑈(1-𝑥 𝑖𝑗 𝑣 ) ∀i ∈ G, ∀ j ∈ {o} ∪ G, ∀v ∈ V, ∀k∈ {1,2 … M} (4.5) 𝑄 𝑜 𝑣 (𝑘) = 0 ∀𝑣 ∈ 𝑉,

Memetic algorithm

We tried to use CPLEX to solve the proposed mathematical model in section 4.2, but only small instances could be solved to optimality in a reasonable computation time.

Since this basic route planning problem of freight buses is NP-hard problem, it is impossible to develop an exact algorithm that can solve the problem to optimality in a reasonable time. Instead, in this section, we design a memetic algorithm (genetic algorithm with local search) for this special periodic vehicle routing problem.

Procedure of the memetic algorithm

Pablo Moscato first proposed the concept of memetic algorithm in 1989. He viewed MA as being close to a form of population-based hybrid genetic algorithm (GA) coupled with an individual learning procedure capable of performing local refinements. And in the context of complex optimization, many different instantiations of memetic algorithms have been reported across a wide range of application domains, in general, converging to high-quality solutions more efficiently than their conventional evolutionary counterparts [START_REF] Samanlioglu | A memetic random-key genetic algorithm for a symmetric multi-objective traveling salesman problem[END_REF][START_REF] Mafarja | Investigating memetic algorithm in solving rough set attribute reduction[END_REF]. So far, MA has been used with great success to solve various vehicle routing problems, including various single period VRPs (capacitated VRP, VRP with time windows, pickup and delivery problem) and the PVRP.

Memetic algorithm design

In this design, we take into account the specific characteristics of this problem: fixed route for each freight bus, the demand of each depot in each period can be split into multiple deliveries, late delivery penalty, etc. The most special features of this design are about the method of encoding and decoding of solutions, the method of calculating the fitness of each solution and the method of local search.

Encoding and decoding of solutions

The encoding of a solution is to transform it into a chromosome, whereas the decoding is to transform a chromosome into a solution in a genetic/memetic algorithm.

In our memetic algorithm, integer string encoding is adopted. For the route planning problem of freight buses with N depots, each chromosome, which is an integer string of length N, is divided into N genes, and each gene represents a depot. The order of the genes in a chromosome will determine the subset of depots, the order of these depots visited by each freight bus [START_REF] Yang | A Lagrangian relaxation approach for a large scale new variant of capacitated clustering problem[END_REF][START_REF] Yalaoui | Efficient methods to schedule reentrant flowshop system[END_REF].

Since the demands of each depot in different periods may be different, the condition that the total demand of a subset of depots visited by a freight bus over M periods does not exceed the capacity of the freight bus times M (i.e., the total capacity of the freight bus over M periods) is not sufficient to ensure that the total demand can be served (delivered) by the freight bus at the end of the M periods. For this reason, we propose the following decoding scheme that takes account of the demand of each depot in each period.

We decode a chromosome from its first gene to its last gene. Through a series of mathematical calculations and checks, the chromosomes are divided into multiple segments, each segment corresponds to the vehicle route of a freight bus. These segments are indexed by integer numbers 1, 2, 3…. according to the order in which they are generated. Figure .4.2 gives an example of the generation of segments. For each segment, its corresponding freight bus starts from the distribution center, visits the depots represented by the genes in the segment and in the order given by the segment, and finally returns to the distribution center.

Fig. 4.2 An example of the generation of segments

For simplicity of explanation, the N genes (depots) in a chromosome are indexed from 1 to N as illustrated in Figure 4.2. With this indexing, the formulas used for the division of a chromosome into segments are given in the following, where the index i corresponds to the i-th gene (depot) in a chromosome and k is the index of a period.

In the formulas, U is the capacity of each freight bus, a and b represents respectively the index of the first gene (depot) and the index of the last gene (depot) in a segment corresponding to the set and the order of depots visited by a freight bus; 𝑠 𝑘 is the sum of the demands of the genes in the segment (the depots visited by the freight bus) in period k, which can be calculated by formula (4.11) ; 𝑞 𝑘 is the total amount of demands of the depots that has not yet been served (delivered) after k visits of the freight bus, which can be calculated by formula (4.12); 𝑤 𝑘 is the capacity not used of the freight bus in period k, which can be calculated by formula (4.13). The formula (4.14) implies that the total demand of the depots in the M periods does not exceed the total available capacity of the freight bus over the M periods minus its total unused capacity, which ensures that the capacity of the freight bus is sufficient to serve (deliver) all the demands of the depots at the end of the M periods.

𝑠 𝑘 = ∑ 𝑑 𝑖 (k) 𝑖∈{𝑎,𝑏} ∀k∈ {1,2 … 𝑀} (4.11) 𝑞 𝑘 = max {𝑞 𝑘-1 + (𝑠 𝑘 -U), 0} 𝑞 0 =0; ∀k∈ {1,2 … 𝑀} (4.12) 𝑤 𝑘 =max {0, U-𝑠 𝑘 -𝑞 𝑘-1 } ∀k∈ {1,2 … 𝑀} (4.13) ∑ 𝑠 𝑘 𝑀 𝑘=1 <= M *U -∑ 𝑤 𝑘 𝑀 𝑘=1 (4.14)
The procedure for dividing a chromosome into segments (routes of freight buses) is given in pseudo code in Algorithm 4.1.

Generation of the initial population

In order to ensure the diversity of population, we generate the initial population randomly (a random integer number between 1 and the number of depots N is assigned to each gene of each chromosome). In general, the number of chromosomes (solutions) generated for the initial population is determined according to the problem size [START_REF] Chen | Modeling, analysis, and optimization of logistics systems petri net based approaches[END_REF][START_REF] Pishvaee | A memetic algorithm for biobjective integrated forward/reverse logistics network design[END_REF]. In our numerical test of the memetic algorithm, we set the population size to be 50~200.

Fitness function

The process of searching for optimal or near-optimal solutions by genetic/memetic algorithm is accompanied by the evolutionary process of chromosomes. In order to evaluate the quality of each chromosome, we need to define its fitness. For our problem, let R denote the set of all routes in a solution (represented by a chromosome), the fitness of the chromosome, denoted by f , is defined as follows:

𝑠 𝑘 (𝑟)= ∑ 𝑑 𝑖 (k) 𝑖∈𝑠𝑒𝑔𝑚𝑒𝑛𝑡(𝑟) ∀k∈ {1,2 … 𝑀}, r ∈ 𝑅 (4.15) 𝑞 𝑘 (𝑟)= max [𝑞 𝑘-1 (𝑟)+ (𝑠 𝑘 (𝑟)-U), 0] 𝑞 0 =0; ∀k∈ {1,2 … 𝑀}; r ∈ 𝑅 (4.16) CP= P*∑ ∑ 𝑞 𝑘 (𝑟) 𝑀 𝑘=1 𝑅 𝑟=1 (4.17) Obj =𝑀 * ∑ ∑ ∑ 𝑐 𝑖𝑗 𝑥 𝑖𝑗 𝑣 𝑣∈𝑉 𝑗∈{𝑠}∪𝐺 𝑖∈{𝑠}∪𝐺 + P*∑ ∑ 𝑞 𝑘 (𝑟) 𝑀 𝑘=1 𝑅 𝑟=1 (4.18) Fitness f =1/Obj (4.19)
The fitness can be calculated with the following steps:

Step1: By the formulas (4.11)-(4.14), we decode a chromosome into a set of segments (routes) R, the genes 𝑠𝑒𝑔𝑚𝑒𝑛𝑡(𝑟) for each segment r, and the vehicle routes of all freight buses.

Step2: By the formulas (4.15)-(4.16), we get the demand 𝑞 𝑘 (𝑟) that has not yet been served (delivered) after k visits of the freight bus for each route (segment) r.

Step 3: By the formulas (4.17), we get the penalty cost CP for the late delivery in M periods for this chromosome (solution).

Step 4: By the formulas (4.18), we get the total cost of the chromosome Obj which includes the operating costs of all freight buses and the penalty cost for the late delivery in M periods.

Step 5: Calculate the fitness 𝑓 of the chromosome by the formula (4.19).

Selection

The task of selection is to choose individuals chromosomes for genetic operations. In this thesis, we choose the best NC (NC is the population size) chromosomes from the pool comprising both the parent and child chromosomes. In this way, good chromosomes are chosen for genetic operations, while avoiding the premature convergence of the memetic algorithm (Amodeo, Chen & EI Hadji, 2008;[START_REF] Jouglet | Hybrid flow-shop: A memetic algorithm using constraint-based scheduling for efficient search[END_REF].

Crossover

Crossover is a randomized method of exchanging certain genes between two chromosomes to produce new chromosomes. Crossover can not only generate new individuals, but also ensure the diversity of the population [START_REF] Hani | Simulation based optimization of a train maintenance facility[END_REF][START_REF] Choong | Metaheuristic methods in hybrid flow shop scheduling problem[END_REF].

In this chapter, we use a method like two-point crossover to exchange some genes between two chromosomes. The repeating genes in the two new chromosomes obtained are then deleted in order to generate feasible solutions. The specific steps of this crossover are given as follows:

Step 1: Randomly choose two chromosomes A1 and B1 to cross.

Step 2: Randomly generate two integers g1 and g2 from the interval [1, N] (N is the total number of genes in each chromosome).

Step 3: Put the segment a1 defined by the genes from g1 to g2 of chromosome A1 in the front of the chromosome B1, and delete all genes in chromosome B1 that repeat the genes in segment a1. This creates a new chromosome B2.

Step 4: Put the segment b1 defined by the genes from g1 to g2 of chromosome B1 in the front of the chromosome A1, and delete all genes in chromosome A1 that repeat the genes in segment b1. This creates a new chromosome A2.

The schematic diagram of crossover is as follows.

Mutation

The mutation operator can make a genetic/memetic algorithm jump out of the current search region and avoid the search to be trapped in a local optimal solution [START_REF] Park | A hybrid genetic algorithm for the job shop scheduling problems[END_REF][START_REF] Mavrovouniotis | Dynamic vehicle routing: A memetic ant colony optimization approach[END_REF]. The specific steps of the mutation used in our algorithm are given as follows:

Step 1: Randomly choose a chromosome A to mutation.

Step 2: Randomly generate two integers g1 and g2 from the interval [1, N] (N is the total number of genes in each chromosome).

Step 3: Reverse the segment s defined by the genes from s1 to s2 of chromosome A in the chromosome. This creates a new chromosome A'.

The schematic diagram of the mutation is given as follows. ), we know that 𝑞 𝑘 (𝑟), the total demand that has not yet been served after visit k of the freight bus, does not depend on the order. Consequently, by formulas (4.17), the penalty cost CP does not depend on the order as well. So, the optimization of each route by local search is equivalent to finding the shortest route for each freight bus that visits all its assigned depots.

Two types of intra-route moves are implemented in our local search procedure, which are illustrated in Fig. 4.6-4.7.

Stop criterion

The memetic algorithm is an iterative search algorithm, so a stop criterion is required to stop its iteration process. In this thesis, we set a maximum number of iterations as the stop criterion for the algorithm [START_REF] Chang | Dynamic programming decision path encoding of genetic algorithms for production allocation problems[END_REF].

Numerical experiments

In order to verify the mathematical model of freight buses routing and evaluate the effectiveness of our Memetic Algorithm, in this section, we design 70 instances in small, medium and large sizes, and compare the performance of the Memetic Algorithm (implemented in MATLAB 2014a with Intel Core i5-4210M CPU 2.6GHz) with that of the MILP solver of CPLEX (CPLEX 12.6)on the instances. In addition, the impact of local search on the algorithm is evaluated and analyzed in this section.

Instance generation

The model of freight buses routing considered in this thesis is related to the We designed 70 instances for the model which are grouped in instances of small size (N∈{7,13}; M∈{3,5}), instances of medium size (N∈{20, 30, 40}; M∈{3,5}) and instances of large size (N ∈ {60, 80}; M ∈ {3,5}) instances(see Table 4.3). For all instances, the following data are taken from the benchmark instances: the coordinates of all nodes, the number of vehicles, and the capacity of each vehicle. The other data are generated randomly or based on the benchmark instances: the demand of each depot in each period, the number of periods M, the unit distance operating cost C, the penalty coefficient P.

For the number of periods M, it is set to 3 or 5. Since it is assumed that all freight buses have the same unit distance operating cost, we simply set C to 1 for all instances.

And the delivery demand of each depot in each period is randomly generated from [1,40]. For the penalty coefficient P, because the ratio of P to C affects the tradeoff between the operating costs of the freight buses and the penalty costs for the late deliveries as well as the service level to customers, i.e., the percentage of customers delivered ontime, we cannot set P too big or too small. After some tests with different P values (P=1, 10, 20, 50, 100), in our numerical experiments we set P to 20 for all instances.

Parameter setting

The parameters of the memetic algorithm were tuned by making a tradeoff between solution quality and CPU time.

For our Memetic Algorithm (MA), we used the method of Taguchi to determine the values of its parameters [START_REF] Tsai | Hybrid Taguchi-Genetic Algorithm for Global Numerical Optimization[END_REF]. After testing the algorithm with the generated instances, the parameters of our MA are chosen as follows. For small instances: population size=80, the probability of crossover=0.9, the probability of mutation=0.1, and the maximum number of iterations=80. For medium instances: population size=100, the probability of crossover=0.8, the probability of mutation=0.05, and the maximum number of iterations=100. For large instances: population size=150, the probability of crossover=0.7, the probability of mutation=0.03, and the maximum number of iterations=150. At the same time, since it is very time consuming for CPEX to find an optimal solution of the freight bus routing model in this chapter even for instances of small size, in order to make the solver of CPLEX able to find a high quality feasible solution of the MILP model for instances of different sizes, we preset its CUP running time to 1000, 1800, 3600, 5400, 7200, 10800, 14400 seconds for instances with 7, 13, 20, 30, 40, 60, 80 depot nodes, respectively.

Experiments and results

Three key values were used to evaluate the performance of our memetic algorithm:

1) The lower bound produced by CPLEX, which indicates a lower bound of the optimal objective value of the MILP model.

2) The best feasible solution of the MILP model found by CPLEX, which is an upper bound of the optimal objective value.

3) The best objective value obtained by the Memetic Algorithm.

The indexes used in the performance evaluation and their definitions are given in

𝐶𝑃𝑈 𝑀𝐴

The CPU time of MA (in seconds)

The following three tables give the experimental results of small size instances, medium size instances, and large size instances, respectively. where each instance is identified by the number of depots and the number of periods. For example, instance 7-3 is an instance with 7 depots and 3 periods.(7-3a,7-3b is the different delivery demands instances with 7 depots and 3 periods) Compared with GA, the average computation time of MA only slightly increases (∆ 𝑐𝑝𝑢 is ranged from 0% to 1.82% with the average percentage of 0.72%) for all sets of instances.

These experimental results show that our memetic algorithm is effective for solving the freight bus routing problem studied in this chapter.

Conclusion

In

Introduction

The problem studied in Chapter 5 is an extension of that studied in Chapter 4. To be more practical and more efficient, freight buses should perform both pickup and delivery of goods at every customer/supplier location they visit. In this chapter, we study the route planning problem of freight buses with pickup and delivery in an urban distribution system. For the vehicle routing problem with pickup and delivery, Bent and Hentenryck (2006) apply Variable Neighbor-hood Search (VNS) to the VRPPD and their computational results show promising performance of their algorithm, compared with the previous PDPTW metaheuristics. [START_REF] Ropke | An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[END_REF] design an ALNS algorithm which proved to be a effective meta-heuristic for the VRPPD, with results reported for up to 1000 customer nodes. ALNS uses several destruction and repair operators to improve the current solution. The neighborhood of a solution can be obtained by deleting few customers from the current solution and re-inserting these customers [START_REF] Demir | An adaptive large neighborhood search heuristic for the Pollution-Routing Problem[END_REF]. In ALNS, the deletion operator and the insertion operator used in each iteration are dynamically selected according to their past performance; each operator is associated with a weight (a fraction). If the operator improves the current solution, its weight increases; Meanwhile, if the newly generated solution conforms to the acceptance criteria defined by ALNS, it is accepted as the current solution for the next iteration. ALNS has been successfully applied to solve various vehicle routing problems (Aksen, Kaya, Salman and Tüncel,2014).

As in Chapter 4, the studied problem is first described. Each freight bus can perform pickup and deliver goods at each depot (customer/supplier location). The freight bus arrives at each customer/supplier location (station), unload goods first and load goods later. During the whole tour, the total amount of goods in the freight bus should not exceed its capacity. The objective is to minimize the operating costs of all freight buses plus the late delivery and pickup penalty costs.

The rest of this chapter is organized as follows. Section 5.2 describes the problem of vehicle route planning of freight buses with both pickup and delivery in urban logistics.

And A mathematical formulation for this route planning problem of freight buses with both pickup and delivery is provided in this section. In section 5.3, we present an ALNS algorithm to solve this special periodic vehicle routing problem with pickup and delivery.

In section 5.4, the relevance of the mathematical model and the effectiveness of the proposed algorithm are proved by numerical experiments. Finally, section 5.5 concludes

Chapter with perspectives for future research.

Problem description and mathematical model

Problem description

Different from the problem description in Chapter 4, in this problem, each freight bus can perform both pickup and delivery of goods at each depot (customer/supplier location) they visit . Key features of this problem are first introduced in the following.

(1)Multiple periods: We consider a time horizon (e.g. one day) that is divided into M periods (M > 1) and assume that each freight bus visits its served depots once in each period, and the demand of delivery and pickup of goods to each depot in each period is known.

(2)Fixed routes: As passenger buses,we assume that each freight bus has a fixed route in the time horizon, and every depot must be served by one freight bus in each period.

(3) Both delivery and pick up: Each freight bus can perform pickup and deliver goods at each depot (customer/supplier location). The freight bus arrives at each customer/supplier location (station), unload goods first and load goods later. During the whole tour, the total amount of goods in the freight bus should not exceed its capacity.

So it is possible that the delivery or the pickup demand of a depot in a period is only partially met in this period because of the capacity limitation of a freight bus, in this case, the unmet demand of the period can be only met in later periods. In other words, the goods loaded or unloaded by the freight bus must be the pickup or delivery demand of this period or the previous periods that were not met due to the limitation of vehicle capacity.

( 4 ) Penalty of delivery/pickup delay. Delivery and pickup of goods at a customer/supplier location can be delayed but with penalties. There are two types of penalty introduced in this model. One is the penalty caused by the delay in the time horizon (e.g. one day) of M periods, which linearly depending on the quantity of the late delivery or pickup demands and the number of periods delayed,with the penalty per period and per unit of demand given by a coefficient 𝛼 (In this thesis, we assume late pickup and delivery have the same penalty coefficient). The other is the penalty for all unmet demands at the end of the time horizon (e.g. one day) of M periods, which linearly depending on the quantity of the late delivery or pickup demands, with the penalty per unit of demand given by another coefficient 𝛽.

In each period, each freight bus leaves from the Distribution Center o, visits its served depots and returns to the Distribution Center. What's more, for one freight bus, every period, all goods loaded at the DC must be unloaded at its served depots before it returns to the Distribution Center; and all goods loaded at its served depots must be unloaded at the Distribution Center when it returns to the DC . In this chapter, it is also assumed that the demand 𝑑 𝑖 (𝑘) and 𝑝 𝑖 (k) of each depot i in each period 𝑘 ∈ {1,2 … 𝑀} is known.

We need to plan the vehicle route for each freight bus v, and the delivery and pickup quantity of each freight bus at each depot in each period. The objective is to minimize the operating costs of all freight buses plus the late delivery and pickup penalty costs.

Mathematical model

In this subsection, we propose a mathematic model for the route planning of freight buses by considering its all characteristics. With this mathematic model, we can optimize the total cost of freight buses composed of their operating costs and penalty costs for the late delivery and pickup of goods in the planning horizon. At the same time, we can also get the optimal routes of freight buses by solving the model.

The detailed mathematical model for the route planning of freight buses is given as follows:

Decision Variables The quantity of all goods remaining to deliver in the freighter bus v 𝜖𝑉 when it just arrives at node i 𝜖{𝑜} ∪ 𝐺 during the k-th visit, k∈ {1,2 … 𝑀}.

• 𝑊 𝑖 𝑣 (k) The quantity of all goods picked up by the freighter bus v ϵV when it just arrives at node i 𝜖{𝑜} ∪ 𝐺 during the k-th visit, k∈ {1,2 … 𝑀}.

Objective Function

The objective is to minimize the total cost including the operating costs of the freight buses and the penalty costs for the late delivery and pickup of goods in the planning time horizon of M periods. ) 𝑣𝜖𝑉 𝑖∈𝐺

(5.1) Subject to : Constraints (5.3) ensure that each freight bus arriving at a depot has to leave it.

∑ x 𝑜𝑗 v 𝑗∈G = ∑ x 𝑗𝑜 v j∈G ∀v ∈ 𝑉 (5.2) ∑ x 𝑖𝑗 v 𝑖∈{o}∪G = ∑ x 𝑗𝑖 v 𝑖∈{0}∪G ∀𝑗 ∈ 𝐺, ∀v ∈ 𝑉 (5.3) ∑ x 𝑖𝑗 v 𝑖∈{o}∪G = y 𝑗 v ∀𝑗 ∈ 𝐺, ∀v ∈ 𝑉 (5.4) ∑ y 𝑗 v v∈V = 1 ∀𝑗 ∈ 𝐺 (5.5) 𝑄 𝑗 𝑣 (𝑘)<=𝑄 𝑖 𝑣 (𝑘)-𝑑 𝑖 𝑣 (𝑘)+𝑈(1-𝑥 𝑖𝑗 𝑣 ) ∀i ∈ G, ∀ j ∈ {o} ∪ G, ∀v ∈ V, ∀k∈ {1,2 … M} (5.6) 𝑄 𝑜 𝑣 (𝑘) = 0 ∀𝑣 ∈ 𝑉, ∀k∈ {1,2 … 𝑀} (5.7) W 𝑗 v (𝑘)>=W 𝑖 v (𝑘)+p 𝑖 v (𝑘)-U(1-x 𝑖𝑗 v ) ∀𝑖 ∈ 𝐺, ∀ 𝑗 ∈ {o} ∪ G, ∀v ∈ 𝑉, ∀k∈ {1,2 … 𝑀} (5.8) W o v (𝑘)= ∑ p 𝑖 v i∈G (𝑘) ∀v ∈ 𝑉, ∀k∈ {1,2 … 𝑀} (5.9) 0<= Q 𝑖 v (𝑘)+ W 𝑖 v (𝑘) <=U 𝑖 ∈ {0} ∪ G,
Constraints (5.4) and (5.5) guarantee that all depots must be served and each depot is served by at most one freight bus. Constraints (5.6) (5.7) and (5.8) (5.9) (5.10) formulate vehicle capacity constraints. Constraints (5.11) (5.12) indicate that in each period, the delivery and pickup of freight bus v at each depot i can only be the demand of that period or earlier periods but cannot be the demand of later periods. Finally, constraints (5.13) define the domains of all decision variables.

Adaptive Large Neighborhood Search (ALNS)

We tried to use CPLEX to solve the proposed mathematical model in section 5.2, but only small instances could be solved to optimality in a reasonable computation time. For this reason, we propose an adaptive large neighborhood search algorithm to solve the route planning problem of freight buses with both pickup and delivery.

Procedure of the ALNS

The large-scale neighborhood search algorithm was first proposed by [START_REF] Shaw | Using constraint programming and local search methods to solve vehicle routing problems[END_REF].

This is an iterative algorithm. The idea of the algorithm is to improve the current solution in each iteration by using a destruction operator that removes some customer nodes from the current routes and a repair operator that reinserts these customer nodes to the routes.

If the new solution is better than the current solution, the former is accepted as the current solution for the next iteration.

ALNS uses multiple destruction and repair operators to improve the current solution in each iteration. The neighborhood of a solution can be obtained by deleting several customer nodes from the current routes (solution) and re-inserting into them the customer nodes. In ALNS, a deletion operator and a re-insertion operator are dynamically selected in each iteration according to their past performance [START_REF] Lv | An iterative algorithm for periodic Sylvester matrix equations[END_REF]; each operator is associated with a probability. If the operator improves the current solution, the probability will increase, otherwise the probability may decrease;

The newly generated solution is accepted if it improves the current solution, otherwise it will be accepted with a probability depending on a temperature and defined according to a Simulation Annealing (SA) rule, the temperature will be gradually decreased with the progress of the algorithm; If the new generated solution is accepted, it will update the current solution for the next iteration. ALNS has been successfully applied to solve various vehicle routing problems (Pisinger and Ropker,2007).

The procedure framework of our ALNS is given in Fig. 5.1.

Fig. 5.1 The procedure framework of ALNS

ALNS design

Taking into account the specific characteristics of our freight buses routing problem with both delivery and pickup, in this section, we design an ALNS to solve the problem.

The most special features of this design are about the method of evaluation of a solution, the method of destroy operators and the method of repair operators.

Initial solution construction

Firstly, we need to generate the initial route for each freight bus. [START_REF] Cordeau | A guide to vehicle routing heuristics[END_REF] analyzed and reviewed methods for generating initial solutions for vehicle routing problems, and classified these methods based on four different aspects, which are generated accuracy, speed, simplicity and elasticity of solutions. After comparison, it is found that the method of Saving Algorithm (Clarke, Wright,1964) has advantages in generating an initial solution quickly and is simple and easy to implement.

For this reason, firstly, we use Saving Algorithm to generate a single giant tour (long route), which contains all the nodes in the distribution system. Next, we randomly divide the long route into k segments (K is the maximum number of freight buses predefined for the system), and each segment corresponds to the initial route of a freight bus. The procedure of construction of the initial solution is given as follows:

Step 1: Apply the Saving Algorithm to construct a giant tour containing all nodes in the distribution system.

Step 2: The giant tour formed in the first step is randomly divided into K-segments (K is the number of freight buses predefined for the distribution system), and each segment corresponds to the initial route of a freight bus.

Evaluation of a solution

When we obtain a solution represented by given values of {𝑥 𝑖𝑗 𝑣 } for the freight bus routing problem in ALNS, we need to evaluate its quality, i.e., the cost of the solution.

Although this cost can be calculated by assigning the values to variables {𝑥 𝑖𝑗 𝑣 } in the model of section 5.2.2 and then solving the derived linear programing model, it is time consuming because such cost evaluation must be done a large number of times in ALNS.

In the following, we provide a much more efficient way to calculate the cost of a solution given the values of {𝑥 𝑖𝑗 𝑣 } under some reasonable assumptions about the operation of the freight buses. We assume all freight buses operate with the two rules: 1) When a freight bus arrives at a depot, it unloads/delivers goods first and then loads/pickup goods from the depot. This order of delivery and pickup can free more capacity for pickup. 2) For delivery, when a freight bus loads goods to be delivered on its route before its departure from the CDC, it gives a higher priority to the demand of a depot to be visited earlier, i.e., it loads goods to be delivered according to the order of depots to be visited on the route; On the other hand, for pickup, every time when a freight bus arrives a depot with pickup demand, it will pick up goods as much as possible, i.e., use as much as possible its remaining capacity to meet the pickup demand. Note that this rule of pickup and delivery will not affect the cost of a solution since we assume late pickup (resp. late delivery) at each depot node has the same penalty coefficient.

With the operation rules, if we know the vehicle route of each freight bus, i.e., the values of 𝑥 𝑖𝑗 𝑣 , in a solution, the delivery demand 𝑑 𝑖 (𝑘) of depot i in the k-th period, the pickup demand 𝑝 𝑖 (𝑘) of depot i in the k-th period, we can calculate the values of variables 𝑑 𝑖 𝑣 (𝑘) and 𝑝 𝑖 𝑣 (𝑘) in the model in section 5.2.2 and then the cost of the solution by the following formulas (5.14)-(5.19).

Calculation of 𝑑 𝑖 𝑣 (𝑘):

Define 𝑑 𝑖 ′ (k) as the sum of the delivery demand of depot i in the k-th period (i. e. , 𝑑 𝑖 (k) ) and the unmet delivery demands of depot i in all previous periods (periods

1 to k-1), k∈ {1,2 … 𝑚}. 𝑑 𝑖 ′ (k)
, which is referred to as the cumulative unmet delivery demand of depot i in the k-th period, can be calculated by the formula:

𝑑 𝑖 ′ (k-1)+ 𝑑 𝑖 (k)-𝑑 𝑖 𝑣 (𝑘 -1) k>=2 𝑑 𝑖 ′ (k)= (5.14) 𝑑 𝑖 (1)
Define 𝐶𝐷 𝑖 𝑣 (k) as the remaining goods to be delivered in freighter bus v when it arrives at node i ϵG on its route in the k-th visit, k∈ {1,2 … 𝑀} . 𝐶𝐷 𝑖 𝑣 (k) can be recursively calculated from the first depot node to the last depot node visited by the freight bus v applying the following formula.

𝐶𝐷 𝑗 𝑣 (k)-𝑑 𝑗 𝑣 (𝑘) for j with x 𝑗𝑖 v =1, j ϵG 𝐶𝐷 𝑖 𝑣 (k)= (5.15) Min [U, S(𝑘) ′ ] for i with x 𝑜𝑖 v =1
where U is the capacity of the freight bus and S(𝑘)′=∑ d 𝑖 ′ 𝑖∈𝐺 (𝑘) * 𝑦 𝑖 𝑣 is the total cumulative undelivered demand of all depots to be visited by freight bus v in the k-th period. In this formula, node j is visited by the freight bus v just before node i. Since each depot can only be visited once by a freight bus in each period, the depot node j in the formula is unique for any given depot node i.

Because goods loaded or unloaded by a freight bus must be the pickup or delivery demand of the current period or those of the previous periods that were not met due to the limited capacity of the freight bus. So 𝑑 𝑖 𝑣 (𝑘) (the quantity unloaded by freighter bus v ϵ𝑉 at the depot i ϵG in the k-th visit ) must take the smaller value between 𝑑 𝑖 ′ (k)

and 𝐶𝐷 𝑖 𝑣 (k).

𝑑 𝑖 𝑣 (𝑘)=min [𝑑 𝑖 ′ (k), 𝐶𝐷 𝑖 𝑣 (k) ] (5.16)
Calculation of 𝑝 𝑖 𝑣 (𝑘):

Define 𝑝 𝑖 ′ (k) as the sum of the pickup demand of depot i in the k-th period (i. e. , 𝑑 𝑖 (k) ) and the unmet pickup demands of depot i in all previous periods (periods 1 to k-1), k∈ {1,2 … 𝑚}. 𝑝 𝑖 ′ (k), which is referred to as the cumulative unmet pickup demand of depot i in the k-th period, can be calculated by the formula:

𝑝 𝑖 ′ (k-1)+ 𝑝 𝑖 (k)-𝑝 𝑖 𝑣 (𝑘 -1) k>=2 𝑝 𝑖 ′ (k)= (5.17) 𝑝 𝑖 (1) k=1
Define 𝐶𝑃 𝑖 𝑣 (k) as the remaining capacity for pickup of the freighter bus v 𝜖𝑉 when it arrives at node i 𝜖𝐺 on its route in the k-th visit, k∈ {1,2 … 𝑀}. 𝐶𝑃 𝑖 𝑣 (k) can be recursively calculated from the first depot node to the last depot node visited by the freight bus v applying the following formula.

𝐶𝑃 𝑗 𝑣 (k)-𝑝 𝑗 𝑣 (𝑘)+ 𝑑 𝑖 𝑣 (𝑘) for j with x 𝑗𝑖 v =1, j ϵG 𝐶𝑃 𝑖 𝑣 (k)= (5.18) U-𝑆 𝑣 (k)+ 𝑑 𝑖 𝑣 (𝑘); for i with x 𝑜𝑖 v =1
where U is the capacity of the freight bus and 𝑆 𝑣 (k)= ∑ 𝑑 𝑖 𝑣 𝑖∈𝐺 (𝑘) 𝑦 𝑖 𝑣 is the cumulative unmet delivery demand of all depots to be visited by freight bus v in the kth period. Similarly, in this formula, node j is visited by the freight bus v just before node i, and node j is unique for any given node i.

So 𝑝 𝑖 𝑣 (𝑘) (the quantity loaded by the freighter bus v ϵ𝑉 at the depot i 𝜖𝐺 in the k-th visit) must also take the smaller value between 𝑝 𝑖 ′ (k) and 𝐶𝑃 𝑖 𝑣 (k), i.e.,

𝑝 𝑖 𝑣 (𝑘)=min [𝑝 𝑖 ′ (k), 𝐶𝑃 𝑖 𝑣 (k) ] (5.19)
On the whole, we can evaluate the cost of a solution by the following steps:

Step1: Apply the formulas (5.14)-(5.16) to calculate the unloaded quantity 𝑑 𝑖 𝑣 (𝑘) of the freighter bus v ϵ𝑉 at the depot i ϵG in its k-th visit k∈ {1,2 … 𝑀};

Step2: Apply the formulas (5.17)-(5.19) to calculate the loaded quantity 𝑝 𝑖 𝑣 (𝑘) of the freighter bus v ϵ𝑉 at the depot i ϵG in its k-th visit k∈ {1,2 … 𝑀};

Step3: Calculate the cost of the solution by applying the formula (5.1) in section 5.2.2;

Adaptive selection of destroy/repair operators

Our ALNS chooses a removal operator and an insertion operator in each iteration by applying the roulette-wheel mechanism. At the beginning all removal operators and all insertion operators are selected with the same probability. In our ALNS algorithm, 8 removal operators and 3 insertion operators are used. Therefore, the probability of initial selection of each removal operator and each insertion operator is 1/8 and 1/3,respectively.

In the process of algorithm execution, the probability of each operator being selected is updated according to the following formula.

𝑝 𝑖 𝑡+1 = 𝑝 𝑖 𝑡 (1-r) +𝑟𝛽 𝑖 𝑡 /𝛼 𝑖 𝑡 (5.20)
𝑝 𝑖 𝑡 is the probability of operator i being selected in the t-th iteration;

𝑟 ∈[0,1] is the Roulette parameter predefined.

𝛼 𝑖

𝑡 is the number of times the operator i was selected in the past t iterations.

𝛽 𝑖

𝑡 is the resulting score of the operator i in the t-th iteration.

The score of an operator is used to measure its performance in each iteration. If a new best solution is found, the score of the operator will increase by Q1;If the solution found is better than the current solution, the score of this operator will increases by Q2;If the solution found is worse than the incumbent solution, the score of this operator will increases by Q3 (Roozbeh, Ozlen, Hearne,2018).

Destroy operators

Our ALNS contains two classes of destroy operators. The first class of destroy operator is to remove a certain number of depots from different routes, which involves 4 destroy operators. The second class of destroy operator chooses one route and then removes all the depots on this route, which involves 4 destroy operators too.

Chapter 5. Route Planning of Freight Buses with both Pickup and Delivery

What's more, for the first class of destroy operators, we will give the number n of all the depots in system and a removal fraction 𝜌 ∈[0,1], each of operators applies a strategy to select /𝜌 * 𝑛/ depots to remove.

Only one destroy operate is executed in each ALNS iteration, the details of those 8 destroy operators are described as following:

1 Random depot Removal

This operator randomly chooses k depots at a time,(k= /𝜌 * 𝑛/,where 𝜌 is a removal fraction, n is the number of depots), removes them from the current vehicle routes, and places them in the removal list LR. This operator helps increase the diversity of solutions.

Worst-distance depot Removal

This operator removes 𝜌 * 𝑛 depots with largest travel distances from different routes. The travel distance of each depot i is defined as 𝐿 𝑗𝑖 + 𝐿 𝑖𝑘 , where node j and k are the depot or the DC visited before depot i and the depot or the DC visited after depot i in the same route, respectively. The depots with the largest travel distances will be removed from the current routes in turn.

Proximity-based Removal

The goal of this operator is to find out a set of depots that have some connection in terms of distance and remove them from the current solution. We use the way of Shaw removal (Shaw,1998)to define the relationship between depots. Firstly, a depot is chosen randomly and we place it in the removal list as the first depot to be removed.

Then the next depot to be removed is the depot closest (Minimum distance) to the last removed depot. After repeating 𝜌 * 𝑛 times Shaw removal , we get all the depots to removal in this operator.

Historical depot Removal

The operator records the distance information of every depot in the past iterations.

The distance of a depot is defined as the sum of distances from the depot before and after the depot (The distance for a depot i is /𝐿 𝑖-1,𝑖 + 𝐿 𝑖,𝑖+1 /). During the execution of our algorithm, the optimal distance of depot i is its minimum distance obtained in all past iterations. This operator removes 𝜌 * 𝑛 depots with the greatest distance difference between the current distance and its optimal distance in each iteration.

Random Route Removal

This operator removes an entire route from the current solution. The route to remove is randomly chosen from all routes in the current solution.

Largest demand Route Removal

This operator first calculates the sum of the delivery and pickup demands for all depots in each route in the current solution, then remove the route which has the largest total demand.

Largest distance Route Removal

This operator calculates the distance traveled by a freight bus in each route, then removes the route which has the largest travel distance.

Least depots Route Removal

This operator calculates the number of depots visited by each route, then removes the route which has the least number of depots served.

Repair operators

Our ALNS algorithm contains three kinds of insertion operators, which are mainly used to re-insert the depots in the removed list into the current solution to generate a new feasible solution. The following describes the function of each insertion operator in detail:

1 Basic Greedy Insertion

The idea of this operator is to insert each depot in the removal list into the best possible route and position. Firstly the insertion distance of each depot i is calculated for each possible route as 𝐿 𝑖 =𝐿 𝑗𝑖 + 𝐿 𝑖𝑘 -𝐿 𝑗𝑘 , where j and k are the node preceding and to node following depot i in the route if i is inserted, then the depot with the lowest insertion Chapter 5. Route Planning of Freight Buses with both Pickup and Delivery distance is selected and inserted into the best route and the best insertion position.

(Goeke, Schneider,2015)

Greedy Insertion with Noise function

This operator is an extension of the basic greedy algorithm, but with a degree of freedom in selecting the insertion route and the insertion position for each depot to insert.

The degree of freedom is realized by appropriately changing the insertion cost (distance)

of each depot by adding a noise. The insertion cost(distance) of each node i becomes 𝐿 𝑖 ′ = 𝐿 𝑖 (The actual insertion cost) + 𝐿 𝑚𝑎𝑥 *u*𝜀(Noise), where 𝐿 𝑚𝑎𝑥 is a constant (the maximum distance between any two depots); u is the noise parameter set to be 0.1 in our numerical experiments, and 𝜀 is a random value between -1 and 1. This operator calculates the modified insertion costs of all depots in the removal list, and then selects the depot with the smallest insertion cost and insert it into the best route and the best position [START_REF] Labadie | The team orienteering problem with time windows: an LP-based granular variable neighborhood search[END_REF].

Greedy Insertion with new route generated

This operator is that combines basic greedy insertion to generate a new route. It consists of two steps: the first step is to randomly select a destroyed depot to connect with the Distribution Centre to form a new route (That is, we first generate a path that only serves one depot); The second step is to insert other destroyed depots into the existing routes according to the basic greedy insertion method introduced in repair operator 1.

Acceptance and stop criterion

The ALNS algorithm proposed in this thesis adopts simulated annealing as the external local search framework. The algorithm framework of the ALNS is given in Algorithm 5.1.The algorithm stops when a specified number of ALNS iterations is reached.

In the Algorithm, 𝑋 𝑏𝑒𝑠𝑡 refers to the best solution found by the algorithm; 𝑋 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 refers to the current solution; 𝑋 𝑛𝑒𝑤 refers to a new temporary solution found in an iteration, which may be discarded or accepted as the current solution for the next iteration. The objective value of a feasible solution X is denoted by f(X). If f(𝑋 𝑛𝑒𝑤 )< f(𝑋 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 ), then 𝑋 𝑛𝑒𝑤 is always accepted, otherwise 𝑋 𝑛𝑒𝑤 will be accepted at a probability of 𝑒 -(𝑓(𝑋 𝑛𝑒𝑤 )-𝑓(𝑋 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 )/𝑇 , where T is the temperature of simulated

Numerical experiments

In order to verify the mathematical model of freight bus routing and evaluate the effectiveness of our ALSN, based on the generated instances in chapter 4 (basic vehicle route planning of freight buses with only delivery), in this section, we also design 70 instances in small, medium and large sizes, and compare the performance of the ALSN (implemented in MATLAB 2014a with Intel Core i5-4210M CPU 2.6GHz) with that of the MILP solver of CPLEX (CPLEX 12.6)on the instances. In addition, the impact of joint distribution realized by this freight buses with both pickup and delivery system on the reduction of transportation costs is evaluated and analyzed in this section.

Instance generation

Based on the generated instances in chapter 4 (basic vehicle route planning of freight buses with only delivery), in this section, we also design 70 instances for the problem which are grouped in instances of small size (N∈{7,13}; M∈{3,5}), instances of medium size (N∈{20, 30, 40}; M∈{3,5}) and instances of large size (N∈{60, 80}; M∈{3,5})

instances. For all instances, the following data are same with the instances in chapter 4

: the coordinates of all nodes, the number of vehicles, and the capacity of each vehicle, the number of periods M, the unit distance operating cost 𝛾.

In order to further evaluate the impact of the joint distribution realized by our freight buses with both pickup and delivery system, we generate the demand of each depot in each period by grouping the customer demands of two private third party logistics companies A and B at the depot in the period, where the demand (both the delivery and pickup) of each company at each depot in each period is randomly generated from [1,20]. At each depot in each period , the demand (both the delivery and pickup) for freight bus is the sum of the demand for company A and B. For the penalty coefficient 𝛼 and 𝛽 , because the ratio of 𝛼 to 𝛾 and 𝛽 to 𝛾 affect the tradeoff between the operating costs of the freight buses and the penalty costs for late delivery and pickup as well as the service level to customers, i.e., the percentage of customer demands delivered/picked up on-time, we cannot set 𝛼 and 𝛽 too big or too small.

After some tests with different 𝛼 and 𝛽 values, in our numerical experiments we set 𝛼 to 20, 𝛽 to 400 for all instances.

Parameter setting

We used CPLEX to solve the MILP model, and used Matlab to implement our ALNS.

Since the ALNS algorithm is composed of several procedures and each procedure has its own parameters, parameter setting was tuned by finding a tradeoff between solution quality and CPU time. The values of the parameters used are listed in Table 5.1.

As we can see from the table, the parameters are divided into three groups. The first group consists of the parameters related to the roulette mechanism, and the second group consists of the parameters related to the simulated annealing. The third group consists of the parameters related to the removal operators and insertion operators [START_REF] Yalaoui | Efficient methods to schedule reentrant flowshop system[END_REF]. Since it is very time consuming for CPEX to find an optimal solution of the freight bus routing model in this chapter even for instances of small size, we preset its CPU running time to 1800,3600, 5400, 7200, 10800, 14400,18000 seconds for instances with 7, 13, 20, 30, 40, 60, 80 depot nodes, respectively.

Experimental results

The indexes used in the performance evaluation of our ALNS and their definitions are given in Table .5.2.

𝐶𝑃𝑈 𝐴𝐿𝑁𝑆

The CPU time of ALNS (in seconds)

The following three tables give the experimental results of small size instances, medium size instances, and large size instances, respectively. Table 5.6 summarizes the average performances of our ALNS and the MILP solver of CPLEX on all instances tested. These experimental results show that our ALNS is effective for solving the freight bus routing problem with both pickup and delivery studied in this chapter.

Impact of the joint distribution realized by freight buses

In this section, in order to preliminarily evaluate the impact of the joint distribution realized by our freight buses system, we compare a system with freight buses with its corresponding system without freight bus.

In the system without freight bus, we assume that there are city freighters operated by two private third party logistics companies A and B, which separately deliver and pickup their customers' demands from a distribution center to multiple depots. Each city freighter of company A or B also visits its served depots once during each period k∈{1,2…M}, and the demand of each company's customers at each depot i in each period must be served by its own city freighters. In each period, each city freighter also begins and ends its travel at the distribution center. What's more, it is also possible that the demand of a depot in a period is totally or partially served in later periods because of the capacity limitation of a city freighter, and there are also two kinds of penalty costs for late delivery and pickup.

To simplify the comparison of the two systems, we assume that all city freighters operated by company A and company B have the same capacity U, the same unit distance operating cost 𝛾, the same penalty coefficient 𝛼 and 𝛽, the same number of periods M in the planning time horizon as those for the freight buses, and all city freighters also have fixed vehicle routes. The objective of each company is to minimize its total cost which includes the operating costs and the penalty costs of its own city freighters. With this assumption, we can use the ALNS proposed in this thesis to optimize the vehicle routes of the city freighters of each company and get its total cost.

The total cost of the system without freight bus is thus the sum of the total costs of company A and B. The following table 5.7 compares the average costs of the two systems. From the results in Table 5.7, we can see that if we use the proposed freight bus system, the cost saving in percentage compared with the corresponding system without freight bus is ranged from 17.6% to 35.3% with the average cost saving 25.1%.

Moreover, we can see that the larger the size of an instance, the more the cost savings of the freight bus system. The experimental results show that the system with freight bus

Chapter 5. Route Planning of Freight Buses with both Pickup and Delivery can significantly reduce transportation costs compared with the system without freight bus.

Conclusions

In this chapter, we have studied the route planning problem of freight buses with both pickup and delivery in an urban distribution system. At first, we have described the operations of freight buses in such a system. Each freight bus can perform pickup and deliver goods at each depot (customer/supplier location). The freight bus arrives at each customer/supplier location (station), unload goods first and load goods later.

During the whole tour, the total amount of goods in the freight bus should not exceed its capacity. The objective is to minimize the operating costs of all freight buses plus the late delivery and pickup penalty costs. In order to solve the problem, a Mixed-Integer Linear Programming (MILP) model is formulated and an Adaptive Large Neighborhood Search (ALNS) algorithm is developed in combination with the characteristics of the problem, and the validity of the model and the effectiveness of our ALNS algorithm is verified through numerical experiments. Moreover, we have also assessed the impact of the joint distribution realized by our freight buses with both pickup and delivery system.

Chapter 4 and Chapter 5 are all the research on the vehicle routing problem of the freight buses with deterministic demands. But in practice, before make the routing planning for freight buses, the delivery demand and pickup demand at each station in each time period of each day are not known, although we can obtain the probabilistic distributions of these demands by statistical analysis of their historical data. So in next chapter 6 we will study the route planning problem of freight buses with stochastic demands.

Introduction

In the traditional route planning problem, it is generally assumed that all information is complete and fixed, that is, the route planner has all the information before, including customer information, road network information and vehicle information, etc., which are fixed during the whole route planning and distribution.

However, before the route construction and during the actual transportation process, all the information is not always known, and it is difficult for the route planner to fully grasp all the information at the nodes. For example, in real work, when we make the routing planning for freight buses, the delivery demand and pickup demand at each station in each time period (for example, from 9:00am to 10:00am) of each day is not known, although we can obtain the probabilistic distributions of these demands by statistical analysis of their historical data. So in this chapter we study the route planning problem of freight buses with stochastic pickup and delivery demands.

The freight bus routing problem with stochastic pickup and delivery demands we study is a very complicated stochastic optimization problem, which is unlikely to be solved by an analytical approach. For this reason, we adopt a scenario-based optimization approach to solve the problem. The scenario approach is related to simulation-based optimization in which an optimization algorithm combined with simulation is used to solve a stochastic optimization problem. In such an approach, simulation experiments are used to evaluate the performance of a system when different values of its input variables (different solutions) are taken, and the algorithm is used as an optimization engine to find the best value of the input variables (the best solution)

of the system in terms of its performance. Monte Carlo simulation is usually used for simulation experiments, which randomly generates a number of possible realizations of random parameters (called Monte Carlo sampling) in a stochastic system (Nguyen and Chen,2018). Each sample (a possible realization of random parameters) in Monte Carlo simulation can be considered a scenario.

The immune genetic algorithm is a hybrid genetic algorithm based on the biological immune system. Unlike the classical genetic algorithm, our IGA has two additional functions: memory function and adjustment function. Different from the standard immune algorithm, genetic operators are introduced in our IGA. The immune genetic algorithm can overcome some disadvantages of genetic algorithms (e.g., prematurity) and improve global search ability and search efficiency. [START_REF] Presbitero | Immune system model calibration by genetic algorithm[END_REF] The rest of this chapter is organized as follows. By adopting the scenario approach, a deterministic equivalence model of the route planning problem of freight buses with stochastic pickup and delivery demands is provided in section 6.3. In section 6.4, we present an Immune Genetic algorithm (IGA) to solve the model approximately with the cost evaluation of each solution based on the model. In section 6.5, the relevance of the mathematical model and the effectiveness of the proposed algorithm are proved by numerical experiments. Finally, in section 6.6, we summarize the main work of this chapter.

Scenario-based optimization

The routing problem of freight buses is NP-hard as most vehicle routing problems.

With stochastic demands, this problem becomes more difficult, which is unlikely to be solved by an analytical approach. So in this chapter, we adopt the scenario-based optimization approach to solve the problem.

The scenario approach is related to simulation-based approach for stochastic optimization, because each sample (a possible realization of random parameters) in Monte Carlo simulation can be considered a scenario. This approach considers a number of scenarios corresponding to possible realizations of random parameters of a stochastic optimization model. For the given scenarios, this stochastic model can be transformed into a deterministic equivalent model, which is solved by an exact or approximate optimization algorithm. We adopt the scenario approach to solve our stochastic freight bus routing problem. In order to do this, we first formulate the deterministic equivalence Mixed-Integer Linear Programming (MILP) model of the stochastic optimization problem for a given number of demand scenarios, and then develop an Immune Genetic Algorithm (IGA) to solve the model approximately with the cost evaluation of each solution based on the model.

The demand scenarios can be generated based on their historical data. By statistical analysis, we can obtain the probability distributions of the pick-up demand and delivery demand of each depot in each time period of each day. The demand scenarios can then be randomly generated according to the probability distributions. If the number of scenarios is taken sufficiently large, we can guarantee that the optimal solution of the deterministic equivalence model is very close to the optimal solution of the stochastic optimization model.

Deterministic equivalence of the stochastics freight bus routing problem

In this section, by adopting the scenario approach, we establish the deterministic equivalence Mixed-Integer Linear Programming (MILP) model of our stochastic freight buses route planning problem for a given number of demand scenarios.

Problem description

As the problem descripted in chapter 5 (section 5.2.1) , in this model, each freight bus can perform both pickup and delivery goods at each depot (customer/supplier location) they visit . However, the difference is that in this chapter both pickup demand and delivery demand are stochastic at each depot.

Through statistical analysis, we can get the probability distributions of the pickup demand and the probability distribution of the delivery demand of each depot in each period. Based on the probability distributions, L demand scenarios corresponding to possible realizations of the pickup and delivery demands of all depots are considered.

We denote by 𝑑 𝑖 (k)(l) the delivery demand of depot i in the k-th period under l-th scenario and by 𝑝 𝑖 (𝑘)(𝑙) the pickup demand of depot i in the k-th period under the l-th scenario. Then, the evaluation of the solution for each vehicle route base on the average expected cost of each freight bus routing scheme in those L groups scenarios. [START_REF] Hammami | A scenario-based stochastic model for supplier selection in global context with multiple buyers, currency fluctuation uncertainties, and price discounts[END_REF][START_REF] Marufuzzaman | Two-stage stochastic programming supply chain model for biodiesel production via wastewater treatment[END_REF].

Deterministic equivalence model

By adopting the scenario approach, we can propose a deterministic equivalence MILP model for our stochastic route planning problem of freight buses. Before presenting the model, we first introduce its decision variables:

Decision Variables • x 𝑖𝑗 v
A binary variable which is equal to 1 if the freight bus v 𝜖𝑉 goes from node i to j (i, j𝜖{𝑜} ∪ 𝐺); and 0 otherwise.

• y 𝑖 v

A binary variable which is equal to 1 if and only if the depot i 𝜖𝐺 is served by the freighter bus v 𝜖𝑉 ; and 0 otherwise.

• 𝑑 𝑖 𝑣 (k)(l)
The quantity unloaded from freight bus v 𝜖𝑉 at the depot i ϵG in its k-th visit (k∈ {1,2 … 𝑀}) under the l-th scenario (l∈ {1,2 … 𝐿}, 0 otherwise.

• 𝑝 𝑖 𝑣 (k)(l)
The quantity loaded to freight bus v 𝜖𝑉 at the depot i 𝜖𝐺 in its k-th visit (k∈ {1,2 … 𝑀}) under the l-th scenario (l∈ {1,2 … 𝐿}; 0 otherwise.

• 𝑄 𝑖 𝑣 (k)(l)
The quantity of all goods remaining to deliver by the freighter bus v 𝜖𝑉 when it just arrives at node i 𝜖{𝑜} ∪ 𝐺 during its k-th visit (k∈ {1,2 … 𝑀}) under the l-th scenario (l∈ {1,2 … 𝐿}.

• 𝑊 𝑖 𝑣 (k)(l)
The quantity of all goods picked up by the freighter bus v 𝜖𝑉 when it just arrives at node i 𝜖{𝑜} ∪ 𝐺 during its k-th visit (k∈ {1,2 … 𝑀}) under the l-th scenario (l∈ {1,2 … 𝐿}.

The objective function of the model, which is to minimize the average total cost including the operating costs of the freight buses and the penalty costs for late delivery and pickup of goods in the planning time horizon of M periods, can be formulated as:

Objective Function Min Obj = [ 𝑀 * 𝐿 * ∑ ∑ ∑ 𝑐 𝑖𝑗 𝑥 𝑖𝑗 𝑣 𝑣∈𝑉 𝑗∈{0}∪𝐺 𝑖∈{𝑜}∪𝐺 + 𝛼 * ∑ ∑ ∑ (∑ 𝑑 𝑖 (𝑘)(𝑙) 𝑛 𝑘=1 -∑ ∑ 𝑑 𝑖 𝑣 (𝑘) 𝑛 𝑘=1 𝑣𝜖𝑉 (𝑙)) 𝑀-1 𝑛=1 𝑙∈{1,2…L} 𝑖∈𝐺 + 𝛽 *∑ ∑ (∑ 𝑑 𝑖 (𝑘)(𝑙) 𝑀 𝑘=1 -∑ ∑ 𝑑 𝑖 𝑣 (𝑘) 𝑀 𝑘=1 (𝑙)) 𝑣𝜖𝑉 𝑙∈{1,2…L} 𝑖∈𝐺 𝛼 * ∑ ∑ ∑ (∑ 𝑝 𝑖 (𝑘) 𝑛 𝑘=1 (𝑙) -∑ ∑ 𝑝 𝑖 𝑣 (𝑘) 𝑛 𝑘=1 𝑣𝜖𝑉 (𝑙)) 𝑀-1 𝑛=1 𝑙∈{1,2…L} 𝑖∈𝐺 + 𝛽 * ∑ ∑ (∑ 𝑑 𝑖 (𝑘)(𝑙) 𝑀 𝑘=1 -∑ ∑ 𝑑 𝑖 𝑣 (𝑘) 𝑀 𝑘=1 (𝑙)) 𝑣𝜖𝑉 𝑙∈{1,2…L} 𝑖∈𝐺 ] /L (6.1)
The constraints of this model can be formulated as : Constraints (6.2) indicate that each freight bus leaves from and returns to the Distribution Center. Constraints (6.3) ensure that each freight bus arriving at a depot has to leave it. Constraints (6.4) and (6.5) guarantee that all depots must be served and each depot is served by at most one freight bus. Constraints (6.6) (6.7) and (6.8) (6.9) (6.10) formulate vehicle capacity constraints. Constraints (6.11) (6.12) indicate that under each scenario, in each period, each freight bus v can only deliver/pick up the demand in that period or earlier periods at each depot visited but cannot deliver/pick up the demand of later periods. Finally, constraints (6.13) define the domains of all decision variables.

Constraints ∑ 𝑥 𝑜𝑗 𝑣 𝑗∈𝐺 = ∑ 𝑥 𝑗𝑜 𝑣 𝑗∈𝐺 ∀𝑣 ∈ 𝑉 (6.2) ∑ 𝑥 𝑖𝑗 𝑣 𝑖∈{𝑜}∪𝐺 = ∑ 𝑥 𝑗𝑖 𝑣 𝑖∈{0}∪𝐺 ∀𝑗 ∈ 𝐺, ∀𝑣 ∈ 𝑉 (6.3) ∑ 𝑥 𝑖𝑗 𝑣 𝑖∈{𝑜}∪𝐺 = 𝑦 𝑗 𝑣 ∀𝑗 ∈ 𝐺, ∀𝑣 ∈ 𝑉 (6.4) ∑ 𝑦 𝑗 𝑣 𝑣∈𝑉 = 1 ∀𝑗 ∈ 𝐺 (6.5) 𝑄 𝑗 𝑣 (𝑘)(𝑙)<=𝑄 𝑖 𝑣 (𝑘)(𝑙)-𝑑 𝑖 𝑣 (𝑘)(𝑙)+𝑈(1-𝑥 𝑖𝑗 𝑣 ) ∀𝑖 ∈ 𝐺, ∀ 𝑗 ∈ {𝑜} ∪ 𝐺, ∀𝑣 ∈ 𝑉, ∀k∈ {1,2 … 𝑀}, ∀l∈ {1,2 … 𝐿} (6.6) 𝑄 𝑜 𝑣 (𝑘)(𝑙) = 0 ∀𝑣 ∈ 𝑉, ∀k∈ {1,2 … 𝑀}, ∀l∈ {1,2 … 𝐿} (6.7) 𝑊 𝑗 𝑣 (𝑘)(𝑙)>=𝑊 𝑖 𝑣 (𝑘)(𝑙)+𝑝 𝑖 𝑣 (𝑘)(𝑙)-𝑈(1-𝑥 𝑖𝑗 𝑣 ) ∀𝑖 ∈ 𝐺, ∀ 𝑗 ∈ {𝑜} ∪ 𝐺, ∀𝑣 ∈ 𝑉, ∀k∈ {1,2 … 𝑀}, ∀l∈ {1,2 … 𝐿} (6.8) 𝑊 𝑜 𝑣 (𝑘)(𝑙)= ∑ 𝑝 𝑖 𝑣 𝑖∈𝐺 (𝑘)(𝑙) ∀𝑣 ∈ 𝑉, ∀k∈ {1,2 … 𝑀} ,

Immune genetic algorithm

The immune genetic algorithm is a hybrid genetic algorithm based on the biological immune system and natural evolution. Unlike a pure genetic algorithm, the memory function and adjustment function of the biological immune system are included in this hybrid algorithm. Also different from a pure immune algorithm, genetic operators are included in the hybrid algorithm. [START_REF] Presbitero | Immune system model calibration by genetic algorithm[END_REF]The immune genetic algorithm can effectively overcome the disadvantages of pure genetic algorithms (e.g., prematurity) and improve global search ability and search efficiency. In the algorithm, the objective function value of the problem corresponds to "antigen'' of the biological immune mechanism, and the solution of the problem corresponds to "antibody" of the biological immune mechanism. The diversity of antibody populations is maintained by immunological selection, which is realized by the immune memory function and self-regulating function of the immune system.( Wang, Geng, Zhang and Ruan,2018)

Principle and procedure of immune genetic algorithm

The procedure framework of our designed Immune Genetic algorithm is shown in Fig. 6.1.

Fig.6.1 Immune Genetic algorithm

The immune system is composed of antigen recognition system, memory mechanism, and antibody promotion and suppression section. In the immune genetic algorithm, antibody population's evolutionary learning process and antigen recognition constitute the optimization process. [START_REF] Ali | An optimization model for product returns using genetic algorithms and artificial immune system[END_REF]The antigen corresponds to the objective function value, and each antibody corresponds to a feasible candidate solution. The matching degree of candidate solutions with respect to the Chapter 6. Route Planning of Freight Buses with Stochastic Demands objective function reflects the affinity between their antigen and antibody, and the higher the matching degree, the greater the affinity and the better the quality of the candidate solutions. The affinity of antibodies is reflected by the similarity between candidate solutions, each antibody group is assessed (evaluated) by its two affinities.

Through selection, crossover, and mutation operation, all antibody groups are updated, and the immune memory mechanism records the optimal antibody group in each generation. Through mutual promotion and inhibition between antibodies, search efficiency is improved and the goal of convergence to the global optimum or high quality near-optimal solutions can be achieved. is composed of a number D + j (j ≥1) and a series of natural numbers less than D+1, this segment represents the j-th route performed by the j-th freight bus, where the order of depots visited by the freight bus is defined by the orders of the natural numbers in the segment. Otherwise, if a segment is composed of only one number D + j without any number denoting a depot, this route is empty, i.e., the j-th freight bus is not used.

Fig.6.2 An example of Antibody coding

For example, suppose that there are 10 depots and 4 freight buses in a distribution system, with D=10 and F=4. The string representing an antibody is given by w = 6-4-3-9-11-12-5-2-1-7-13-8-10 (see the figure 4). By adding D+ F in the front of w, we can get w' = 14-6-4-3-9-11-12-5-2-1-7-13-8-10 which can be divided into 4 segments: 14-6-4-3-9, 11, 12-5-2-1-7, and 13-8-10, so the freight bus routes represented by this antibody are given as follows: the freight bus 4 visits the depots 6, 4, 3, 9 successively; the freight bus 1 does not visit any depot; the freight bus 2 visits the depots 5, 2, 1, 7 successively; and the freight bus 3 visits the depots 8, 10 successively.

Note that we use w instead of w' to represent an antibody string (a solution of the freight bus routing problem) is because if w' is used, a new antibody string generated by cross-over may have its first number less than D+1, i.e., a depot number, which is not consistent with the format of w'. Otherwise, if w is used, such inconsistence problem will not happen.

continuous method:The formula for calculating the affinity 𝑆 𝑤,𝑥 between antibody w and antibody x is defined as follows.

𝑆 𝑤,𝑥 =𝐾 𝑤,𝑥 /(D+F-1)

(6.15)
where 𝐾 𝑤,𝑥 is the number of same digits appeared in both the antibody w and the antibody x, and D+F-1 is the antibody length. For example, for the antibody 1 represented by the string [642531] and the antibody 2 represented by the string [632512],

their antibody-antibody affinity 𝐾 1,2 is 3, because there are 3 identical digits (6, 2, 5) in the two antibodies (Wang, Geng, Zhang and Ruan,2018).

Calculation of antibody concentration

For each antibody w, its antibody concentration 𝐶 𝑤 , which reflects the proportion of similar antibodies in the population, is defined as:

𝐶 𝑤 = 1/N*(∑ 𝑆 𝑤,𝑥 ′ 𝑥∈𝑁 ) (6.16)
Where 𝑆 𝑤,𝑥 ′ ={ 1, 𝑆 𝑤,𝑥 ≥ 𝑇 0, 𝑆 𝑤,𝑥 < 𝑇 ,

where T is a preset threshold and N is the total number of antibodies. In our numerical experiments, we set T to be 0.7 for all instances.

The sum of all antibody concentrations is given by SC=∑ 𝐶 𝑤 𝑤∈𝑁 .

Inhibition and promotion of antibodies

The inhibition and promotion of antibodies are not only based on the fitness of an antibody but also based on its concentration (diversity) with respect to all other antibodies.

The promotion and inhibition of antibodies is realized by changing the expected reproductive probability of antibodies. In a population of antibodies, the expected reproductive probability of each individual w is determined by both its fitness 𝐴 𝑤 and its antibody concentration 𝐶 𝑤 . Let 𝑝 𝑤 denote the expected reproductive probability of antibody w, 𝑝 𝑤 is defined as follows:

𝑝 𝑤 =𝜇*𝐴 𝑤 /SA+(1-𝜇)* 𝑒 -𝐶 𝑤 (6.17)
where μ is a constant between 0 and 1. In our numerical experiments, we set μ to 0.6 for all instances.

It can be seen from the above formula that the higher the antibody fitness 𝐴 𝑤 , the greater the expected reproduction probability 𝑝 𝑤 ; the greater the antibody concentration 𝐶 𝑤 , the smaller the expected reproduction probability 𝑝 𝑤 . This implies that the updating of 𝑝 𝑤 not only promotes antibodies with high fitness, but also inhibits antibodies with high concentrations to ensure the diversity of the antibody population), which helps to increase the search efficiency in each iteration and further reduce the number of iterations required to obtain a high quality solution [START_REF] Presbitero | Immune system model calibration by genetic algorithm[END_REF].

Genetic manipulation

Through genetic manipulations, new progeny antibodies can be generated. The genetic manipulations are realized in three steps: selection, crossover and mutation, which are explained as follows:

1)Selection

The task of selection is to choose parent antibodies for evolution. In our numerical experiments, we choose the best N (N is the population size) antibodies from the antibody pool comprising both the parent and child antibodies based on their expected reproduction probability (calculated by the formula (6.17)). In this way, promising antibodies are chosen for evolution.

2) Crossover

In this thesis, we use a method like two-point crossover to exchange some digits (genes) between two antibodies. The obtained repeating genes in the two new antibodies are then deleted in order to generate feasible antibodies (solutions).

3)Mutation

The mutation operation can make a genetic algorithm jump out of the current search region and then avoid the search to be trapped in a local optimal solution. As the example in Fig. 6.2, the Reverse method is used in our Mutation Operation.

Fig.6.3 An example of Mutation operation

The genetic manipulations follow the immunization operations in each iteration of the immune genetic algorithm. After the genetic operations, the newly generated progeny antibodies and the antibodies in the memory library together form a new generation of antibody population.

Stop Criterion

A stop criterion is required to stop its iteration process. In our numerical experiments, we adopt a maximum number of iterations, denoted by Maxiter, as the stop criterion for the algorithm [START_REF] Chang | Dynamic programming decision path encoding of genetic algorithms for production allocation problems[END_REF].

The Pseudo-code of our Immune Genetic algorithm metaheuristic can be seen in Algorithm 6.1.

5:

The top m antibodies (in the term of fitness)are stored in the memory library.

6:

Calculate the antibody concentration 𝐶 𝑤 for each antibody w the formula (6.16)

7:

Calculate the expected reproductive probability of antibodies 𝑝 𝑤 of each antibody w by the formula (6.17)

8:

Select the parent antibodies based on expected reproductive probability 𝑝 𝑤 of each antibody w.

9:

Perform crossover and mutation operations on the parent antibodies with the probability of crossover 𝑃 𝑐 and the probability of mutation 𝑃 𝑚 10: Update the population with the newly generated progeny antibodies and the antibodies in the memory library.

11: end for

Numerical experiments

Based on the generated instances in chapter 4 and 5, in this chapter, we design 14 sets of instances of small, medium and large sizes, and compare the performance of the Immune Genetic algorithm (implemented in MATLAB 2014a with Intel Core i5-4210M CPU 2.6GHz) with that of the MILP solver of CPLEX 12.6 on the instances. In addition, we compare of the performances of IGA and GA in the section 6.5.5.

Instance generation

Based on the generated instances in chapter 5(route planning problem of freight buses with both pickup and delivery), in this chapter, we generated 14 sets of instances long preset time aims to ensure that the resolution of the MIP model can obtain at least one feasible solution served as a comparison indicator with our algorithm, although in most cases it failed to achieve such a goal.

Determination of the number of scenarios by Monte Carlo Sampling Method

By adopting the scenario approach, a stochastic optimization problem is transformed into a deterministic optimization problem called deterministic equivalence model. However, if the number of scenarios is too large, the resolution of the deterministic equivalence model requires an enormous memory and computational effort. Using a statistical method introduced in Shapiro and Homem-de Mello (1998),

we are able to determine the minimum number of scenarios required to obtain a solution within a confidence interval for a given level of confidence 𝛼. Based on the theory of probability, this approach provides a relationship between the reliability of the obtained solution and the number of scenarios. Let 𝜎(𝑛) denote the sampling variance 𝜎(𝑛)

obtained with n scenarios (samples) given as follows:

( )   ( )

2 1 E cos cos 1 n s s t t n n  = - = -  (6.18)
Where 𝑐𝑜𝑠𝑡 𝑠 is the system cost obtained under scenario (sample) s. For a given confidence interval with length H and a given level of confidence 𝛼, the minimum number of scenarios N required can be calculated by:

( ) 2 /2 Z n N H       =     (6.19)
where value 𝑍 𝛼/2 is determined by Pr(Z<=𝑍 𝛼/2 )=1-α/2, where Z is the random variable subject to the standard normal distribution N(0, 1). In summary, the procedure for determining the minimum number of scenarios is given as follows:

1) Generate a small number of n (n>=30) demand scenarios (samples), and solve the deterministic equivalence model in Section 6.3.2 for each scenario s to get However, for the other instances (N=7, M=5; N=13,M=3;and N=13,M=5),no proven optimal solution was obtained by CPLEX. In this case, we can only compare the nearoptimal solutions obtained by the two methods and their running times. We can see for those instances the Immune Genetic algorithm could find a better solutions than CPLEX with an average percentage improvement 𝐼𝑚𝑝 𝐼𝐺𝐴-𝐶𝑝𝑙𝑒𝑥 of 10.05% in terms of total cost. Furthermore, our Immune Genetic algorithm has a much shorter running time than CPLEX.

𝑐𝑜𝑠𝑡 𝑠 .
Table 6.3 compares the performances of the two solution methods for medium size instances. With the increase of the number of depots, the relative gap 𝐺𝑎𝑝 𝐶𝑝𝑙𝑒𝑥 between the upper bound and the lower bound obtained by CPLEX rapidly grows from 17.65% to 52.67%, whereas our Immune Genetic algorithm has a relatively smaller change of the relative gap 𝐺𝑎𝑝 𝐼𝐺𝐴 from 7.28% to 16.48%. As a result, there is a significant increase in the improvement 𝐼𝑚𝑝 𝐼𝐺𝐴-𝐶𝑝𝑙𝑒𝑥 from 10.07% to 82.72%. For the sets of instances with N=30, M=5 and N=40, M=5, we can see CPLEX failed to find a feasible solution, even after a long running of 6h to 7h. By contrast, our Immune Genetic algorithm could always find a better feasible solutions. Although the running time of the IGA increases from 2089.7 seconds to 2696.7 seconds, it is much shorter than that of CPLEX for all instances.

Table 6.4 compares the results obtained by two methods for large size instances. We can see CPLEX failed to find a feasible solution for all the instances with a preset running time. For most of the instances, CPLEX stopped due to out of memory. In this case, we can only compare the lower bound LB produced by CPLEX and the upper bound 𝐼𝐺𝐴 𝑂𝑏𝑗 found by the Immune Genetic algorithm. For the large size instances, we can see our Immune Genetic algorithm could produce a solution with an average gap 𝐺𝑎𝑝 𝐼𝐺𝐴 of 17.71% between 𝐼𝐺𝐴 𝑂𝑏𝑗 and the lower bound LB, our algorithm outperforms CPLEX very significantly in terms of CPU time.

Comparison of the performances of IGA and GA.

In this section, In order to evaluate the advantage of the introduction of the immune functions in our Immune Genetic algorithm, we also compare our IGA with GA without Immune functions (memory function and adjustment function) on the instances considered. Table 6.5 compares the average performances of the two algorithms, where

CostIGA , CostGA and CUPIGA, CUPGA respectively denote the average cost and the average computation time of IGA and GA for each set of instances, and 𝐼𝑚𝑝 𝐼𝐺𝐴 = (CostGA -CostIGA )/ CostIGA*100, ∆ 𝑐𝑝𝑢 =(CPUIGA -CPUGA )/ CPUIGA*100. The relative improvement of IGA over GA in terms of cost reduction, denoted by 𝐼𝑚𝑝 𝐼𝐺𝐴 , reflects the immune functions in IGA. From this table, we can see for the sets of instances with N=7, M=3 and N=7, M=5), GA and IGA could obtain the same results, and GA took less computation time. However, for the medium and large instances, we can see 𝐼𝑚𝑝 𝐼𝐺𝐴 is ranged from 1.86% to 6.28% with the average percentage improvement 4.74%. Compared with GA, the average computation time of IGA only slightly increases for all sets of instances (∆ 𝑐𝑝𝑢 is ranged from 0.88% to 1.75% with the average percentage of 1.28%) for all sets of instances.

These computational results show that our Immune Genetic algorithm is much more effective than CPLEX for solving the freight bus routing problem with stochastic demands studied in this thesis.

Conclusions

Chapter

Perspectives

As a preliminary study of freight buses, there are still many research works remaining to do in order to implement freight buses in reality.

Firstly, this thesis only analyzes the economic benefits (joint distribution) of freight buses versus city freighters in terms of transportation cost reduction. To prove other potential advantages of freight buses such as schedule regularity, traffic congestion reduction, and use of fast lanes, more quantitative analysis is required. Due to the lack of real data, we have not taken into account of the use of fast lanes in our freight bus routing models, which will be the next step of our study on freight bus.

Secondly, in chapter 4, 5and 6, we have proposed one metaheuristic algorithm for each of the three variants of the freight bus routing problem. Since all we study are new variants of periodic vehicle routing problem, we could not compare these algorithms with other algorithms in the literature on benchmark instances, because such algorithms and benchmark instances do not exist. So in the future, we should either develop more heuristic algorithms, evaluate and compare them with real data, or improve the algorithms proposed in this thesis.

Thirdly, in the environment of electronic commerce, the requirements for timely distribution may be different for different customers, so in the future, we should consider the freight bus routing problem with different priorities for different freight transportation demands in order to meet the diversified market demands. With different priorities for different pickup/delivery demands, the penalty costs for the late services of these demands will be different, which will greatly increase the complexity of the routing problem to solve, which needs us to further improve the existing models and algorithms.

Finally, in the routing problems we have studied, each freight bus station is only visited by one freight bus for regular service. In the future, according to different freight volumes at different stations, we may consider the freight bus routing problem where some stations (depots) are passed (visited) by multiple freight bus lines.

Just like passenger buses, with the rapid development of e-commerce and urbanization, and the increase of freight transportation demands in a city center, we believe that freight buses will play an important role in modern urban distribution systems. We hope that we can conduct a better and deeper study of the freight routing problem in a project of the real implementation of a urban logistics system with freight buses in the future.

A.1 Introduction générale

Plus de moitié de la population mondiale vit actuellement dans des zones urbaines.

L'Organisation Mondiale de la Santé prévoit que la population des zones urbaines continuera de croître de plus de 1.5% par an jusqu'en 2030 (OMS, 2010) [START_REF] Christofides | Exact algorithms for the vehicle routing problem based on spanning tree and shortest path relaxations[END_REF][START_REF] Laporte | . An exact algorithm for the asymmetrical capacitated vehicle routing problem[END_REF]Lapone, 1992) et des algorithmes heuristiques (Gendreau, 1994;[START_REF] Baker | A genetic algorithm for the vehicle routing problem.Computers[END_REF][START_REF] Prins | A simple and effective evolutionary algorithm for the vehicle routing problem.Computers& Operations Research[END_REF] pour résoudre ces problèmes. Étant donné que les algorithmes exacts ne peuvent traiter que des problème de tournées de véhicules de petite taille avec environ 50 clients et que le temps de calcul de ces algorithmes augmente de manière exponentielle avec l'augmentation de la taille du problème, ils ne peuvent pas être utilisés pour résoudre des problème de tournées de véhicules de grande taille. Par conséquent, la plupart des spécialistes se tournent vers les algorithmes heuristiques, qui visent à trouver une solution satisfaisante à un PRV dans un temps de calcul satisfaisant.

Logistique collaborative a attiré une attention croissante au cours des dernières années, souvent conduit par le potentiel important de réduction des coûts et d'incertitude, et de préoccupations environnementales [START_REF] Verdonck | Collaborative logistics from the perspective of road transportation companies[END_REF][START_REF] Du | Liner shipping fleet deployment with sustainable collaborative transportation[END_REF] Dans commentaires connexes de Verdonck et al. (2013) et Cruijssen et al. (2007c).

Les deux traitent de collaborations en matière de transport. Cependant, [START_REF] Verdonck | Collaborative logistics from the perspective of road transportation companies[END_REF] se concentrent uniquement sur la planification opérationnelle des transporteurs routiers (c'est-à-dire les propriétaires et les exploitants de matériel de transport). La perspective des expéditeurs collaborateurs (c'est-à-dire les propriétaires des envois) n'est pas prise en compte. L'examen de Guajardo et Ronnqvist ( 2016) traite de la répartition des coûts dans le transport collaboratif, qui constitue également un aspect important de la tournée collaborative de véhicules.

A.3 Bus de fret dans la logistique urbaine

Avec l'augmentation de la distribution de fret dans les transports urbains et sous l'effet de la demande du marché, de plus en plus de cargos de villes privées sont nés dans les centres-villes, ce qui rend leur trafic plus dense et la pollution de l'air plus grave dans les zones métropolitaines. Motivés par la distribution conjointe, nous avons présenté dans ce mémoire de thèse le concept de bus de fret, un nouveau moyen de transport en commun pour la logistique urbaine qui peut remplacer les cargos appartenant à différentes entreprises privées de logistique tierce au centre-ville [START_REF] Dai | Mathematical model and solution approach for collaborative logistics in less than truckload (LTL) transportation[END_REF]. Dans les deux figures suivantes, les cargos urbains sont comparés aux bus de fret dans les systèmes de distribution urbains.

En tant que service public pour les entreprises de logistique tierces et les clients, l'utilisation de bus de fret peut permettre une distribution conjointe. Les principaux paramètres du modèle sont définis comme suit:

• o Le centre de distribution d'où chaque bus de fret part et revient.

• 𝑉 Ensemble des bus de fret.

• G Ensemble de dépôts.

• 𝑈 La capacité de chaque bus de fret.

• 𝐶 𝑖𝑗 Coût de fonctionnement d'un bus de fret lorsqu'il passe d'un noeud i à un noeud j (i, jϵ{s} ∪ 𝐺).

• M Le nombre de périodes prises en compte dans le problème de planification d'itinéraire.

• 𝑑 𝑖 (k) La demande du dépôt i pendant la k-ième période, 𝑖 ∈ G, 𝑘 ∈ {1,2 … 𝑀}. (1) Plusieurs périodes: nous considérons un horizon temporel (par exemple un jour) divisé en M périodes (M> 1) et supposons que chaque bus de fret visite ses dépôts desservis une fois par période, ainsi que la demande de livraison et de ramassage des marchandises. Marchandises à chaque dépôt à chaque période est connue.

+ P* ∑ ∑ (∑ 𝑑 𝑖 (𝑘) 𝑛 𝑘=1 -∑ ∑ 𝑑 𝑖 𝑣 (𝑘) 𝑛 𝑘=1 𝑣𝜖𝑉 𝑀 𝑛=1 𝑖∈𝐺 ) Constraints ∑ x 𝑜𝑗 v 𝑗∈G = ∑ x 𝑗𝑜 v j∈G ∀v ∈ 𝑉 (4.1) ∑ x 𝑖𝑗 v 𝑖∈{o}∪G = ∑ x 𝑗𝑖 v 𝑖∈{0}∪G ∀𝑗 ∈ 𝐺, ∀v ∈ 𝑉 (4.2) ∑ x 𝑖𝑗 v 𝑖∈{o}∪G = y 𝑗 v ∀𝑗 ∈ 𝐺, ∀v ∈ 𝑉 (4.3) ∑ y 𝑗 v v∈V = 1 ∀𝑗 ∈ 𝐺 (4.4) 𝑄 𝑗 𝑣 (𝑘)>=𝑄 𝑖 𝑣 (𝑘)+𝑑 𝑗 𝑣 (𝑘)-𝑈(1-𝑥 𝑖𝑗 𝑣 ) ∀i ∈ G, ∀ j ∈ {o} ∪ G, ∀v ∈ V,
(2) Routes itinéraires fixes: comme bus de passagers, nous supposons que chaque bus de fret a un itinéraire fixe dans l'horizon temporel et que chaque dépôt doit être desservi par un bus de fret à chaque période.

( ) [START_REF] Pisinger | A general heuristic for vehicle routing problems[END_REF].

𝑣𝜖𝑉 𝑖∈𝐺 𝛼 * ∑ ∑ (∑ 𝑝 𝑖 (𝑘) 𝑛 𝑘=1 -∑ ∑ 𝑝 𝑖 𝑣 (𝑘) 𝑛 𝑘=1 𝑣𝜖𝑉 𝑀-1 𝑛=1 𝑖∈𝐺 ) + 𝛽 * ∑ ( ∑ 𝑝 𝑖 (𝑘) 𝑀 𝑘=1 -∑ ∑ 𝑝 𝑖 𝑣 (𝑘) 𝑀 𝑘=1 ) 𝑣𝜖𝑉 𝑖∈𝐺 (5.1) Constraints ∑ x 𝑜𝑗 v 𝑗∈G = ∑ x 𝑗𝑜 v j∈G ∀v ∈ 𝑉 (5.2) ∑ x 𝑖𝑗 v 𝑖∈{o}∪G = ∑ x 𝑗𝑖 v 𝑖∈{0}∪G ∀𝑗 ∈ 𝐺, ∀v ∈ 𝑉 (5.3) ∑ x 𝑖𝑗 v 𝑖∈{o}∪G = y 𝑗 v ∀𝑗 ∈ 𝐺, ∀v ∈ 𝑉 (5.4) ∑ y 𝑗 v v∈V = 1 ∀𝑗 ∈ 𝐺 (5.5) 𝑄 𝑗 𝑣 (𝑘)<=𝑄 𝑖 𝑣 (𝑘)-𝑑 𝑖 𝑣 (𝑘)+𝑈(1-𝑥 𝑖𝑗 𝑣 ) ∀i ∈ G, ∀ j ∈ {o} ∪ G, ∀v ∈ V, ∀k∈ {1,2 … M} (5.6) 𝑄 𝑜 𝑣 (𝑘) = 0 ∀𝑣 ∈ 𝑉, ∀k∈ {1,2 … 𝑀} (5.7) W 𝑗 v (𝑘)>=W 𝑖 v (𝑘)+p 𝑖 v (𝑘)-U(1-x 𝑖𝑗 v ) ∀𝑖 ∈ 𝐺, ∀ 𝑗 ∈ {o} ∪ G, ∀v ∈ 𝑉, ∀k∈ {1,2 … 𝑀} (5.8) W o v (𝑘)= ∑ p 𝑖 v i∈G (𝑘) ∀v ∈ 𝑉, ∀k∈ {1,2 … 𝑀} (5.9) 0<= Q 𝑖 v (𝑘)+ W 𝑖 v (𝑘) <=U 𝑖 ∈ {0} ∪ G,
Le cadre de procédure de notre système ALNS est présenté à la Fig. 5.1. Les contraintes (6.2) indiquent que chaque bus de fret part et revient au centre de distribution. Les contraintes (6.3) garantissent que chaque bus de fret arrivant à un dépôt doit le quitter. Les contraintes (6.4) et (6.5) garantissent que tous les dépôts doivent être desservis et que chaque dépôt est desservi par au plus un bus de fret. Les contraintes (6.6) (6.7) et (6.8) (6.9) (6.10) définissent les contraintes de capacité des véhicules. Les contraintes (6.11) (6.12) indiquent que pour chaque période, la livraison et le ramassage des bus de fret v à chaque dépôt i ne peuvent être que la demande de cette période ou de périodes antérieures, mais ne peuvent pas être la demande de périodes ultérieures. Enfin, les contraintes (6.13) définissent les domaines de toutes les variables de décision.

A.7.2 Perspectives

En tant qu'une étude préliminaire sur les bus de fret, il reste encore beaucoup à faire pour améliorer la recherche sur nos bus de fret.

Premièrement, cette thèse analyse uniquement les avantages économiques des bus de fret par rapport aux cargos de ville en termes de réduction de coûts de transport au chapitre 5. Pour vérifier d'autres avantages potentiels des bus de fret tels que les horaires réguliers, la réduction de l'embouteillage et l'utilisation de voies rapides dédiées au bus de passagers, une analyse quantitative est également requise. En raison du manque de données réelles, nous n'avons pas pris en compte l'utilisation de voies rapides dans notre modèle d'itinéraire de bus de fret, qui constituera une prochaine étape de notre étude sur les bus de fret. Enfin, dans nos recherches sur l'tournées des véhicules, une gare des bus de fret n'a besoin que d'un bus de fret pour un service régulier; À l'avenir, en fonction des différentes demandes de fret des différentes gares, nous pouvons considérer le problème de tournées des véhicules sous le service de plusieurs lignes de bus de fret dans certaines gares.

Tout comme les bus, avec le développement rapide du commerce électronique et de Ecole Doctorale "Sciences pour l'Ingénieur"

Thèse réalisée en partenariat entre :

Fig. 1 . 1

 11 Fig. 1.1 Organization of this thesis ................................................................................

Fig. 2 . 1

 21 Fig. 2.1 An example of vehicle routing problem .........................................................Fig. 2.2 The schema of ALNS...................................................................................... Fig. 3.1 Two-tiered system ......................................................................................... Fig.3.2 Three-tiered system ..........................................................................................

Fig. 3

 3 Fig. 3.3 City freighters in an urban distribution system ..............................................

Fig. 3

 3 Fig. 3.4 Freight buses in an urban distribution system ................................................ Fig.3.5 An example of freight buses lines....................................................................

Fig. 3 . 6

 36 Fig.3.6 The structure of freight bus logistics system ...................................................

Fig. 4

 4 Fig.4.1 Memetic Algorithm..........................................................................................

Fig. 4 . 2

 42 Fig.4.2 An example of the generation of segments ......................................................Fig.4.3 Crossover ......................................................................................................... Fig.4.4 Mutation........................................................................................................... Fig.4.5 An example of the assignment of freight buses to depots ............................... Fig.4.6 The 2-Opt Operator..........................................................................................

Fig. 5 . 1

 51 Fig.5.1 The procedure framework of ALNS ................................................................ Fig.6.1 Immune Genetic algorithm ............................................................................

Fig. 6 . 2

 62 Fig.6.2 An example of Antibody coding ....................................................................

Fig. 6 . 3

 63 Fig.6.3 An example of Mutation ................................................................................

Fig. 1

 1 Fig. 1.1. Organization of this thesis Chapter 1 mainly introduces the research background and significance of this thesis, and introduces the main research contents and the organization of this thesis.Chapter 2 gives a literature review of the research related to this thesis, with a

  2.3.2 Metaheuristic algorithms .....................................................................................18 2.4 Collaborative logistics.

  Collaborative urban transportation .........................................................................26

  designed a scanning algorithm to solve the problem of random tugboat scheduling for port barges. In 1989, Dror et al. gave a brief review of the model and algorithm of VRPSD. Subsequently, in 1992, Dror et al. studied the inventory routing problem of fuel companies with uncertain fuel demands. Johnson

  studied the vehicle routing problem with stochastic service time under the condition of on-time delivery, established a stochastic programming model with the objective of minimizing the total transportation cost, and solved it by the iterative tabu algorithm under the condition of guaranteeing the minimum on-time delivery probability of all customers. Binart et al. (2016) studied the vehicle routing problem with stochastic service and travel time with priority, and solved the problem by a 2-stage method consisting of planning stage and execution stage.. C Vehicle Routing Problem with Stochastic Customers Bertsimas et al. (1993) studied the vehicle routing problem in the case of stochastic customers. Bent et al. (2004) studied the stochastic vehicle routing problem with the goal of maximizing the number of service customers, and solved it by the multi-scene method. Sambola et al. (2007) studied the stochastic location-routing problem of customers, and proposed a two-stage heuristic algorithm. The first stage was the Chapter 2. Literature Review construction stage, which was used to determine the open parking lot and provide a

  studied the vehicle routing problem for garbage collection with time windows, which took the driver's lunch break into account, and increased the route compactness and work pressure balance goal in addition to minimizing the number of vehicles and vehicle travel time. Zhou et al. (2015) studied the multi-objective time window problem with minimizing the number of vehicles and the total service time of vehicles on the longest route. Chiang et al. (2014) used the evolutionary algorithm to solve the problem of multi-objective time window. Favaretto et al. (2007) studied the non-full load multi-time windows problem with limited maximum travel time, and solved the problem by ant colony algorithm.

  solved the VRP, the crossover operator uses edge recombination exchange, while the mutation operator uses local search operators 2-Opt, 3-Opt, Or-Opt. Pablo Moscato first proposed the concept of memetic algorithm in 1989. He viewed MA as being close to a form of population-based hybrid genetic algorithm (GA) coupled with an individual learning procedure capable of performing local refinements.

Fig. 3

 3 Fig. 3.1. Two-tiered system Fig.3.2. Three-tiered system

  Fig. 3.3 City freighters in an urban distribution system

Fig. 3 . 6

 36 Fig.3.6 The structure of freight bus logistics system

  ..................................................................................................................42 4.2 Problem description and mathematical model ........................................................43 4.2.1 Problem description .............................................................................................43 4.2.2 Mathematical model ............................................................................................45 4.3 Memetic algorithm ......................................................................................................47 4.3.1 Procedure of the memetic algorithm .................................................................47 4.3.2 Memetic algorithm design ..................................................................................48 4.4 Numerical experiments ...............................................................................................56 4.4.1 Instance generation ..............................................................................................57 4.4.2 Parameter setting ..................................................................................................58 4.4.3 Experiments and results ......................................................................................58 4.4.4 Impact of the local search ...................................................................................644.5 Conclusion....................................................................................................................66

Chapter 4 .

 4 Basic Route Planning of Freight Buses with only Delivery (MILP) problem and then develop a memetic algorithm (genetic algorithm with local search) to solve it near-optimally. Our development of this memetic algorithm takes into consideration specific characteristics of the freight bus routing problem, such as fixed route for each freight bus, demand that can be served in a later period but with a late delivery penalty cost, etc. Moreover, we use problem-tailored methods to code/decode, calculate the fitness of each solution, and to perform local search in this algorithm. In order to verify the model and evaluate the performance of the algorithm, we then conduct numerical experiments on instances generated based on benchmark instances and analyze the numerical results. Through the experiments, we have proved the relevance of the mathematical model and the effectiveness of the proposed memetic algorithm.

  Fig.4.1 Memetic Algorithm

Algorithm 4. 1 -

 1 Division operation for a chromosome 1 a←1, b ← 𝑎, r←0 2 for b← a to N do 3 Calculate 𝑠 𝑘 , 𝑞 𝑘 , 𝑤 𝑘 by formulas (4.11) to (4.13) As shown in Algorithm 4.1, for a chromosome, if the genes from 1 to b-1 satisfy the formula (4.14), and the genes from 1 to b cannot satisfy the formula (4.14), then we get the first segment segment(1) which consists of the genes from 1 to b-1, This means all the depots represented by genes from 1 to b-1 in the chromosome will be visited by the first freight bus, and the depot represented by the gene b will be visited by the second freight bus. To get the second segment or the set and the order of the depots to be visited by the second freight bus, we check the genes starting from the gene b with the formulas (4.11) to (4.14) again until the constraint (4.14) is violated. This procedure is repeated until the last gene N of the chromosome is checked. At the end of this procedure, the chromosome is divided into several segments, each segment corresponds to the route of a freight bus.

Fig

  Fig.4.3 Crossover

Fig

  Fig.4.4 Mutation

Fig. 4 . 5

 45 Fig.4.5 An example of the assignment of freight buses to depots

Fig. 4 . 6

 46 Fig.4. 6 The 2-Opt Exchange Operator

Chapter 4 .

 4 Basic Route Planning of Freight Buses with only Delivery

4. 4 . 4

 44 Impact of the local searchIn order to analyze the impact of local search on our memetic algorithm (MA), we also tested the instances considered in section 4.4.1 with the genetic algorithm without local search (GA). Table4.7 compares the average performances of the two algorithms, where CostAVG and CUPAVG respectively denote the average cost and the average computation time for each set of instances, and 𝐼𝑚𝑝 𝐿𝑆 = (CostAVG(𝐺𝐴 ) -CostAVG (𝑀𝐴))/ CostAGV(𝑀𝐴 )*100, ∆ 𝑐𝑝𝑢 =(CPUAVG(𝑀𝐴) -CPUAVG (𝐺𝐴))/ CPUAGV(𝑀𝐴 )*100.

  this chapter, we have studied the basic route planning of freight buses with only delivery. After an analysis of the characteristics of the problem and the literature of vehicle routing problems, we recognize this problem is a new variant of periodic vehicle routing problem. The problem is first described under some assumptions on the operation of freight buses and a Mixed-Integer Linear Programming (MILP) model is then formulated for it. In order to solve the problem, a memetic algorithm (genetic algorithm with local search) is developed. The relevance of the mathematical model and the effectiveness of the proposed memetic algorithm are proved by numerical experiments. However, in practice,as a new public transportation means for urban logistics, freight buses should perform both pickup and delivery of goods at every customer/supplier location they visit. In the next chapter, we will research the route planning problem of freight buses with both pickup and delivery. ..................................................................................................................68 5.2 Problem description and mathematical model ........................................................69 5.2.1 Problem description .............................................................................................69 5.2.2 Mathematical model ............................................................................................70 5.3 Adaptive Large Neighborhood Search (ALNS) .......................................................73 5.3.1 Procedure of the ALNS .......................................................................................73 5.3.2 ALNS design .........................................................................................................74 5.4 Numerical experiments ...............................................................................................84 5.4.1 Instance generation ..............................................................................................84 5.4.2 Parameter setting ..................................................................................................85 5.4.3 Experimental results ............................................................................................86 5.4.4 Impact of the joint distribution realized by freight buses ...............................92 5.5 Conclusions ..................................................................................................................94

Chapter 5 .

 5 Route Planning of Freight Buses with both Pickup and Delivery

  Let D = |G| and F = |V| denote the number of depots and the number of freight buses, respectively. For the freight buses route planning problem studied, D depots are represented by natural numbers from 1 to D; F freight buses are represented by natural numbers from D+1 to D+F, where D+1 denotes the first freight bus and D+F denotes the last freight bus. Each solution of the problem is represented by an antibody w which is a string of non-repeating natural numbers between 1 and D+F-1 with the length of D+F-1. For each antibody string w, let w' denote the string generated from w by adding in front of it the number D+F denoting the last freight bus. The extended string w' can be divided into F segments corresponding F routes with possible empty routes. Each segment contains one and only one number lager than or equal to D+1 which indicate a freight bus or a route. Each segment starts with such a number which either follows a series of natural numbers less than D+1 denoting depots or follows nothing. If a segment

Algorithm 6. 1 -

 1 Pseudo-code of the Immune Genetic algorithm metaheuristic 1: Generate N Initial Solutions 2: Initialize the probability of crossover 𝑃 𝑐 , the probability of mutation 𝑃 𝑚 , the size of memory library m 3: for iter ←1 to Maxiters do 4: Calculate the antibody fitness 𝐴 𝑤 based on the scenario-based deterministic equivalence model in section 6.3.2 and the proposed Method in section 5.3.2.2 (Evaluation of a solution).

  4 and Chapter 5 are all the research on the vehicle routing problem of the freight buses with deterministic demands. But in practice, before we arrange the freight bus route, we don't know the exact delivery and pickup demand of each depot in each period. So base on the research in chapter 4 and 5, in this chapter we further study the route planning problem of freight buses with stochastic demands, this problem is solved by using a scenario-based optimization(SBO) Method. Combining with Monte Carlo simulation, we establish the corresponding mathematical model, and design an Immune Genetic algorithm(IGA). the validity of the model and the effectiveness of our algorithm is verified through numerical experiments. Moreover, we have also compare the performances of IGA and GA in our research.However, in this thesis, we have not quantitatively analyzed the advantages of freight buses over city freighters owned by private third-party logistics companies in terms of on-time delivery or pickup, traffic congestion reduction, and use of fast lanes.And the effectiveness of freight buses needs to be further evaluated by considering other factors. In next chapter, we will summarizes all the work of this thesis, and points out the future research direction on the basis of analyzing the shortcomings of this research. development of e-commerce and urbanization, more and more city freighters operated by different private third-party logistics companies were born and circulate in the centers of cities, which makes traffic congestions and air pollutions more and more severe in metropolitan areas.Motivated by joint distribution, in Chapter 3, we put forward for the first time the concept of freight bus, which is a new public transportation means for urban logistics that can replace city freighters belonging to different private third-party logistics companies in the center of a metropolitan city such as Beijing and Shanghai. Just like buses for passengers, freight buses can be also run by the city government and provide a public service for urban logistics. In Chapter 3, we describes the facilities and equipment required for the implementation of a freight bus system and its operation management. We also conduct a macroscopic analysis of the advantages of using freight buses in collaborative transportation, especially in timely distribution, increase of road utilization and other aspects in comparison with city freighter. Chapter 4 studies the basic vehicle routing problem of freight buses with only delivery demands. It is a new variant of periodic vehicle routing problem. In order to solve the problem, a Mixed-Integer Linear Programming (MILP) model is formulated and a memetic algorithm (genetic algorithm with local search) is developed. The relevance of the mathematical model and the effectiveness of the proposed memetic algorithm are proved by numerical experiments. In Chapter 5, we consider a more general freight bus routing problem with the consideration of both pickup and delivery demands. As in Chapter 4, we first establish a Mixed-Integer Linear Programming (MILP) model for the problem and then develop an Adaptive Large Neighborhood Search (ALNS) algorithm to solve it. The validity of the model and the effectiveness of our ALNS algorithm are verified through numerical experiments.Chapter 4 and Chapter 5 study the route planning problem of freight buses with deterministic demands. Since in practice, before we plan the routes for freight buses, we may not know the exact delivery and pickup demands of each depot in each period of each day, so we study the freight bus routing problem with stochastic pickup and delivery demands in Chapter 6. By adopting the scenario-based optimization approach, this problem is solved by using an Immune Genetic algorithm (IGA) with the cost of each solution evaluated based on a deterministic equivalence model. For a given number of demand scenarios, we first establish the corresponding deterministic equivalence model, and then develop the Immune Genetic algorithm (IGA). The relevance of the mathematical model and the effectiveness of the proposed algorithm are proved by numerical experiments.

Fig. 5

 5 Fig.5.1 Le cadre de procédure de ALNS Afin de vérifier le modèle mathématique de la planification d'itinéraires des bus de fret et d'évaluer l'efficacité de notre ALSN, sur la base des instances générées au chapitre 4, nous avons également conçu 70 instances de petites, moyennes et grandes tailles, et comparé les performances du ALSN (implémenté dans MATLAB) avec celui du résolveur MILP de CPLEX sur les instances. Pour tous les cas, nous pouvons voir notre ALNS a un grand avantage sur CPLEX en termes de temps d'exécution. Pour les petites instances, nous pouvons constater que ALNS a trouvé de meilleures solutions que CPLEX avec un pourcentage moyen d'amélioration 𝐼𝑚𝑝 𝑀𝐴-𝐶𝑝𝑙𝑒𝑥 de 25,94% en termes de coût total. Pour les instances de taille moyenne, l'amélioration 𝐼𝑚𝑝 𝑀𝐴-𝐶𝑝𝑙𝑒𝑥 est passée de 31,82% à 55,67%. Pour les instances de grande taille, nous pouvons voir que nos solutions ALNS offrent un écart moyen 𝐺𝑎𝑝 𝐴𝐿𝑁𝑆 de 17,04% et que la meilleure amélioration 𝐼𝑚𝑝 𝐴𝐿𝑁𝑆-𝐶𝑝𝑙𝑒𝑥 de l'ALNS par rapport à CPLEX pourrait atteindre 116,62%. Ces résultats expérimentaux montrent que notre système ALNS est efficace pour résoudre le problème de la planification d'itinéraires de bus de fret étudié dans cette thèse.

A. 6 . 4

 64 Fig.6.1 Algorithme génétique immunitaire Sur la base des instances générées dans les chapitres 4 et 5, nous avons généré dans ce chapitre 14 ensembles d'instances pour le problème, regroupées dans des instances de petite taille, instances de taille moyenne et instances de grande taille. Pour les petites instances, nous pouvons voir que l'algorithme Immune Génétique pourrait trouver de meilleures solutions que CPLEX avec un pourcentage moyen d'amélioration 𝐼𝑚𝑝 𝐼𝐺𝐴-𝐶𝑝𝑙𝑒𝑥 de 12,01% en termes de coût total. De plus, nous pouvons voir que notre algorithme immunitaire génétique a un temps d'exécution beaucoup plus court que CPLEX. Pour les instances de taille moyenne, il y a une augmentation significative de l'amélioration 𝐼𝑚𝑝 𝐼𝐺𝐴-𝐶𝑝𝑙𝑒𝑥 de 10,07% à 82,72%. Pour les grandes instances, nous pouvons constater que CPLEX n'a pas réussi à trouver une solution réalisable pour toutes les instances avec une durée d'exécution prédéfinie. Dans ce cas, nous ne pouvons comparer que la limite inférieure LB produite par CPLEX et la limite

  Deuxièmement, dans chaque chapitre 4,5 et 6, nous avons proposé un type d'algorithme méta-heuristique pour chaque variante du problème. Notre recherche sur les bus de fret étant une nouvelle variante du problème de tournées de véhicules périodique, nous n'avons aucun moyen de le comparer avec d'autres algorithmes conçus ou exemple de référence. Ainsi, dans la suite de notre étude, nous devrions développer davantage d'algorithmes heuristiques, de les comparer et de les tester avec des données réelles, ou améliorer nos algorithmes conçus.Troisièmement, dans le contexte du commerce électronique, les exigences de ponctualité de distribution peut être différentes selon les clients. Dans nos futures recherches, nous devrons donc examiner le problème de tournées dans le cas d'une demande de fret de priorité différente afin de répondre à la demande diversifiée du marché. Sous la demande de fret de priorité différente, les retards de cargaison seront différents, ce qui augmentera considérablement la difficulté de résolution du problème et nécessitera une amélioration supplémentaire des modèles et des algorithmes existants.

  l'urbanisation et l'augmentation de la demande de transport de marchandises dans le centre-ville, nous pensons que bus de fret va jouer un rôle important dans le système de distribution urbain moderne. Espérons qu'à l'avenir, nous pourrons mener une étude meilleure et plus approfondie sur la construction d'un système logistique de bus de fret en ville. and difficulties of practical implementation of horizontal collaboration in logistics.Int. Trans. Oper. Res., 26, 775-793. Bektas, T., Crainic, T. G., & Van Woensel, T. (2017).From managing urban freight to smart urban logistics networks. In Network design and optimization for smart cities (pp. 143-188). World Scientific. Bent, R., & Hentemyck,P.V.(2004).A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows. Transportation Science, 38(4):515-530. Bent, R.,&Hentenryck,P.V. (2006). A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows, Computers & Operations Research, 33, 875-893. Bent, R. W., & Hentenryck, P. V. (2004). Scenario-Based Planning for Partially Dynamic Vehicle Routing With Stochastic Customers. Operations Research, Modèles et algorithmes pour la planification d'itinéraire de bus de fret Dans cette thèse, les bus de fret sont introduits comme un nouveau moyen de transport collectif pour la logistique urbaine. Tout comme les autobus, les bus de fret sont des véhicules normalisés avec les itinéraires et les horaires fixes. Grace aux services stables et précis fournis par ces bus de fret, les expéditeurs et les consommateurs peuvent organiser de manière flexible les délais de livraison et de ramassage de leurs commandes. Le problème de planification d'itinéraires de bus de fret pour la distribution urbaine est étudié, où chaque bus de fret effectue répétitivement un circuit partant d'un centre de distribution, se rendant à plusieurs dépôts et retournant au centre. Ce problème est une nouvelle variante du problème de tournées périodiques de véhicules, qui n'a jamais été étudiée dans la littérature. Nous avons étudié trois variantes du problème de planification d'itinéraires de bus de fret : le problème de base avec demandes de livraison uniquement, le problème avec ramassages et livraisons, et le problème avec demandes de ramassage et de livraison stochastiques. Pour chaque variante du problème, après avoir établi un modèle mathématique, nous avons développé un algorithme métaheuristique pour la résoudre. Le choix de chaque algorithme prend en compte les caractéristiques de la variante correspondante du problème étudiée. La pertinence des modèles et lroutes and time schedules. With stable and accurate services provided by freight buses, both shippers and customers can flexibly arrange their order delivery times. The route planning problem of freight buses for urban distribution is studied, where each freight bus repeatedly performs a tour that leaves from a distribution center, visits multiple depots, and returns to the center. This problem is a new variant of periodic vehicle routing problem, which was never studied in the literature. We have studied three variants of the freight bus routing planning problem: the basic freight bus routing problem with only deliveries, the freight bus routing problem with both pickups and deliveries, and the freight bus routing problem with stochastic demands. For each variant of the problem, after establishing its mathematical model, we have developed a metaheuristic algorithm to solve it. These metaheuristic algorithms include a memetic algorithm, an adaptive large neighborhood search algorithm, and an immune genetic algorithm combined with scenario-based optimization for cost evaluation. The choice of each algorithm considers the characteristics of the corresponding variant of the problem studied. The relevance of the mathematical models and the effectiveness of the proposed algo

Freight Bus in Urban Logistics Contents 3

  .1 Proposal of freight bus in urban logistics ................................................................30 3.1.1 Key issues in our urban logistics........................................................................30 3.1.2 Three-tiered distribution system ........................................................................31 3.1.3 Introduction of freight bus in urban logistics ...................................................33 Operation management of freight bus system ..................................................

	there is increasing scope to use these systems for transporting freight. However, they
	survey light-goods also discuss the limitations: light rail systems cannot provide door-to-door services and CHAPTER 3
	vehicles and analyze their rather negative impact on urban areas. Bektas , Crainic, and lack last-mile transportation. Furthermore, some light rail systems already operate at
	Van Woensel (2017) provide an overview of efforts from different perspectives: system maximum capacity to serve passenger demand. (Basso et.al, 2019)
	(infrastructure), planning problems, and business models. The authors also summarize Therefore, we need to explore new solutions for the problems of how to carry out
	optimization methods that support planning and operation of urban transportation cooperative transportation more effectively and how to improve the service level of
	systems. They emphasize that innovations such as standardized containers,combined urban logistics..
	passenger and freight transportation could improve future urban delivery. Savelsbergh
	and Van Woensel (2016) give the most recent overview from the perspective of OR,
	and discuss trends that include the increase of e-commerce, need for speed,
	sustainability, the sharing economy, population growth, and technological
	advancements. The authors also consider the multi-level problem, which is at the core
	of synchronizing different levels and modes for vertical collaboration in urban
	transportation systems.
	Verdonck et al. (2013) and Cruijssen et al. (2007c) have related reviews. They both 3.1.4 Advantage of freight bus system ........................................................................35
	deal with transportation collaborations. However, Verdonck et al. (2013) only focus on
	the operational planning of road transportation carriers (i.e. the owners and operators 3.2 Implementation issues of the freight bus system .....................................................36
	of transportation equipment). The perspective of collaborating shippers (i.e. the owners 3.2.1 Infrastructure of freight bus system ...................................................................36
	of the shipments) is not considered. Guajardo and Ronnqvist (2016) comment on cost
	allocation in collaborative transportation, which is also an important aspect in 3.2.2
	collaborative vehicle routing.
	Rail infrastructure is usually provided in urban areas, but not used to realize freight
	deliveries. Motraghi and Marinov (2012) develop an event-based simulation model to
	study the advantages of using urban light rail networks for freight transportation. They
	investigate two scenarios, adding either scheduled or flexible freight trains. Dampier
	and Marinov (2015) discuss using a metropolitan railway network to transport freight
	directly to a city center for the example of Newcastle upon Tyne, UK. They compare
	traditional modes of transportation, inter-modal transport, urban logistics, and rail
	transport. They claim that many cities in the UK have existing light rail networks, and

39 Chapter 3. Freight Bus in Urban Logistics

Table 3

 3

	First tier	urban vehicle	urban vehicle
	Second tier electro-tricycle	city freighter
	Third tier	×	electro-tricycle

.1. Vehicles used in different tiers Two-tiered system Three-tiered system

  Capacitated Vehicle Routing Problem. So when generating the instances, we use some data from the benchmark instances of Capacitated Vehicle Routing Problem provided

by Augerat et al. and Christofides et al. at http://neo.lcc.uma.es/vrp/. However, since the freight bus routing model involves multiple periods, we have to generate demand data randomly based on the benchmark data.

Table 4 .1

 4 Parameter Setting of the MA.

	Parameter	Small	Medium	Large
	Population size	80	100	150
	Probability of crossover	0.9	0.8	0.7
	Probability of mutation	0.1	0.05	0.03
	Maximum number of iterations	80	100	150

Table 4 .

 4 2.

		Table 4.2 Performance indexes.
	Abbreviation	Definition
	𝐶𝑝𝑙𝑒𝑥 𝑂𝑏𝑗	The best feasible objective value found by CPLEX in a preset running time
	LB	The lower bound produced by CPLEX in a preset running time
	𝑀𝐴 𝑂𝑏𝑗	The best feasible objective value obtained by MA after a preset number of iterations
	𝐺𝑎𝑝

𝐶𝑝𝑙𝑒𝑥

The gap between 𝐶𝑝𝑙𝑒𝑥 𝑂𝑏𝑗 and LB, which is defined as

(𝐶𝑝𝑙𝑒𝑥 𝑂𝑏𝑗 -LB)/ 𝐶𝑝𝑙𝑒𝑥 𝑂𝑏𝑗 *100

𝐺𝑎𝑝 𝑀𝐴

The gap between 𝑀𝐴 𝑂𝑏𝑗 and LB, which is defined as (𝑀𝐴 𝑂𝑏𝑗 -LB)/ 𝑀𝐴 𝑂𝑏𝑗 *100

𝐼𝑚𝑝 𝑀𝐴-𝐶𝑝𝑙𝑒𝑥

The improvement (cost reduction) of 𝑀𝐴 𝑜𝑏𝑗 over 𝐶𝑝𝑙𝑒𝑥 𝑂𝑏𝑗 , which is defined as (𝐶𝑝𝑙𝑒𝑥 𝑂𝑏𝑗 -𝑀𝐴 𝑜𝑏𝑗 )/ 𝑀𝐴 𝑂𝑏𝑗 *100

𝐶𝑃𝑈 𝐶𝑝𝑙𝑒𝑥

The CPU time of CPLEX (in seconds)

Table 4 .3

 4 Experimental results of small size instances. Instances 𝐶𝑝𝑙𝑒𝑥 𝑂𝑏𝑗 LB 𝑀𝐴 𝑂𝑏𝑗 𝐺𝑎𝑝 𝐶𝑝𝑙𝑒𝑥 𝐺𝑎𝑝 𝑀𝐴 𝐼𝑚𝑝 𝑀𝐴-𝐶𝑝𝑙𝑒𝑥 𝐶𝑃𝑈 𝐶𝑝𝑙𝑒𝑥 𝐶𝑃𝑈 𝑀𝐴 Experimental results of medium size instances.Table 4.5. Experimental results of large size instances. methods and their running times. Comparing their three indexes (𝐺𝑎𝑝 𝐶𝑝𝑙𝑒𝑥 , 𝐺𝑎𝑝 𝑀𝐴 and 𝐼𝑚𝑝 𝑀𝐴-𝐶𝑝𝑙𝑒𝑥 ), we can see that MA found better solutions than CPLEX with an average percentage improvement 𝐼𝑚𝑝 𝑀𝐴-𝐶𝑝𝑙𝑒𝑥 of 19.13% in terms of total cost. Furthermore, we can see our MA algorithm supersedes CPLEX in terms of running time, the longest CPU time for MA is only 37.2 seconds compared with the limit of 1800 seconds reached by CPLEX. Table 4.4 gives in the same format the results for medium size instances. With the increase of the number of depot nodes, the gap of CPLEX 𝐺𝑎𝑝 𝐶𝑝𝑙𝑒𝑥 , has a rapid growth from 21.78% to 50.63%, while our MA looks more stable with a relatively smaller change from 5.59% and 18.41%. As a result, there is a significant increase in the improvement 𝐼𝑚𝑝 𝑀𝐴-𝐶𝑝𝑙𝑒𝑥 from 18.04% to 62.10%. For the instances with N=30, M=5 𝑀𝐴 𝑂𝑏𝑗 ). For large size instances, we can see our MA produced solutions with an average gap 𝐺𝑎𝑝 𝑀𝐴 of 14.44%, and the best improvement 𝐼𝑚𝑝 𝑀𝐴-𝐶𝑝𝑙𝑒𝑥 of the MA over CPLEX could reach 119.11%. The average performances of the two solution methods.

	7-3a	853.7	853.7	853.7	0.00	0.00 0.00	57.5	5.3
	7-3b	789.3	789.3	789.3	0.00	0.00 0.00	56.3	5.2
	7-3c	861.5	861.5	861.5	0.00	0.00 0.00	57.8	4.7
	7-3d	773.6	773.6	773.6	0.00	0.00 0.00	58.6	5.0
	7-3e	824.8	824.8	824.8	0.00	0.00 0.00	56.9	5.1
	7-5a	1587.3 1587.3 1587.3 0.00	0.00 0.00	189.7 16.8
	7-5b	1556.1 1556.1 1556.1 0.00	0.00 0.00	203.2 15.8
	7-5c	1509.6 1509.6 1509.6 0.00	0.00 0.00	179.1 14.3
	7-5d	1552.3 1552.3 1552.3 0.00	0.00 0.00	196.5 15.3
	7-5e	1517.3 1517.3 1517.3 0.00	0.00 0.00	183.4 16.3
	13-3a	1140.6 919.3	996.3	19.40	7.73 14.48	1800	20.5
	13-3b	1186.8 981.2	1098.6 17.33	10.69 8.03	1800	21.7
	13-3c	1406.3 1125.5 1246.7 19.97	9.72 12.80	1800	19.6
	13-3d	1091.7 907.9	996.3	16.83	8.87 9.58	1800	23.4
	13-3e	2249.0 1865.4 1998.7 17.06	6.67 12.52	1800	21.1
	13-5a	2938.4 2022.4 2256.4 31.17	10.37 30.23	1800	37.1
	13-5b	2525.6 1763.2 2028.3 30.19	13.07 24.52	1800	33.7
	13-5c	2601.2 1768.0 2006.6 32.03	11.89 29.63	1800	35.8
	13-5d	2658.4 1990.2 2154.1 25.14	7.61 23.41	1800	37.2
	13-5e	2660.6 1909.8 2109.6 28.22	9.47 26.12	1800	34.5
	Table 4.4 Instances 𝐶𝑝𝑙𝑒𝑥 𝑂𝑏𝑗 LB	𝑀𝐴 𝑂𝑏𝑗 𝐺𝑎𝑝 𝐶𝑝𝑙𝑒𝑥 𝐺𝑎𝑝 𝑀𝐴 𝐼𝑚𝑝 𝑀𝐴-𝐶𝑝𝑙𝑒𝑥 𝐶𝑃𝑈 𝐶𝑝𝑙𝑒𝑥 𝐶𝑃𝑈 𝑀𝐴
	20-3a	2185.2 1709.3 1851.3 21.78	7.67 18.04	3600	105.1
	20-3b	2283.5 1686.1 1785.9 26.16	5.59 27.86	3600	127.9

N=7, M=5 (7-5), both MA and CPLEX can solve the model to optimality, and our MA consumed less CPU time than CPLEX. When the number of depot nodes increases to 13, no proven optima was obtained. In this case, we compare near-optimal solutions of the two (30-5) and N=40, M=5 (40-5), we can see CPLEX failed to find a feasible solution, even after a long running of 1.5h or 2h. In contrast, our MA always returned better quality feasible solutions. In parallel, the running time of the MA grows naturally with instance size but still represents a small fraction of the CPU time consumed by CPLEX. Table

4

.5 gives the experimental results for large size instances. We can see CPLEX failed to find a feasible solution for 16 out of 20 instances with a preset running time.

For most of the instances, CPLEX terminated because of lack of memory, so we did not try longer time limit. In this case, we can only compare the lower bound LB produced by CPLEX and the upper bound found by the MA (

Table 4 .

 4 6 concludes the average value of 𝐺𝑎𝑝 𝐶𝑝𝑙𝑒𝑥 , 𝐺𝑎𝑝 𝑀𝐴 , and 𝐼𝑚𝑝 𝑀𝐴-𝑐𝑝𝑙𝑒𝑥

by instance size, respectively.

Table 4 .7

 4 Comparison of the average performances of GA and MA. The relative improvement of MA over GA in terms of cost reduction, denoted by 𝐼𝑚𝑝 𝐿𝑆 in Table 4.7, reflects the effect of local search. From the table, we can see 𝐼𝑚𝑝 𝐿𝑆 is ranged from 0% to 7.33% with the average percentage improvement 4.71%.

			GA		MA
	Instance sets					𝐼𝑚𝑝 𝐿𝑆	∆ cpu
		CostAVG	CPUAVG	CostAVG	CPUAVG
	7-3	820.6	5.1	820.6	5.1	0.00	0.00
	7-5	1544.5	15.7	1544.5	15.7	0.00	0.00
	13-3	1316.5	21.3	1267.3	21.3	3.88	0.00
	13-5	2202.4	35.6	2111.0	35.7	4.33	0.28
	20-3	1853.3	106.9	1782.3	107.3	3.98	0.37
	20-5	3001.8	165.8	2859.5	166.8	4.98	0.60
	30-3	2470.6	218.9	2354.2	220.1	4.94	0.55
	30-5	4207.9	301.9	3979.4	304.3	5.74	0.79
	40-3	2805.7	396.9	2653.6	400.1	5.73	0.80
	40-5	4828.0	519.3	4528.7	524.9	6.61	1.07
	60-3	4526.1	705.3	4284.4	712.3	5.64	0.98
	60-5	7763.3	1002.2	7270.3	1016.5	6.78	1.41
	80-3	5736.9	910.2	5414.5	923.7	5.95	1.46
	80-5	9873.9	1213.1	9199.5	1235.6	7.33	1.82

Route Planning of Freight Buses with both Pickup and Delivery

	Chapter 5. 𝛽 * ∑ ( ∑ 𝑀 𝑘=1	𝑝 𝑖 (𝑘)	-∑ ∑ 𝑀 𝑘=1	𝑝 𝑖 𝑣 (𝑘)
	Min Obj =	𝑀 * ∑ 𝑖∈{𝑜}∪𝐺	∑ 𝑗∈{0}∪𝐺	∑ 𝑣∈𝑉	𝑐 𝑖𝑗 𝑥 𝑖𝑗 𝑣	+
	𝛼 * ∑ ∑ 𝑀-1 (∑ 𝑛 𝑘=1 𝑛=1 𝑖∈𝐺	𝑑 𝑖 (𝑘)	-∑ ∑ 𝑛 𝑘=1 𝑣𝜖𝑉	𝑑 𝑖 𝑣 (𝑘)	)	+
		𝛽 *∑ ( ∑ 𝑀 𝑘=1 𝑖∈𝐺	𝑑 𝑖 (𝑘)	-∑ ∑ 𝑀 𝑘=1 𝑣𝜖𝑉	𝑑 𝑖 𝑣 (𝑘)	)
	𝛼 * ∑ ∑ 𝑀-1 (∑ 𝑛 𝑘=1 𝑛=1 𝑖∈𝐺	𝑝 𝑖 (𝑘)	-∑ ∑ 𝑛 𝑘=1 𝑣𝜖𝑉	𝑝 𝑖 𝑣 (𝑘)	) +

  annealing, set initially as f(𝑋 𝑖𝑛𝑖𝑡 ) * 𝑃 𝑖𝑛𝑖𝑡 , where f(𝑋 𝑖𝑛𝑖𝑡 ) is the objective value of the initial solution, and 𝑃 𝑖𝑛𝑖𝑡 is a constant. The cooling rate of the simulated annealing is denoted by h, and h∈ (0,1) is a given parameter. The algorithm returns the best solution

	12:	𝑋 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 ← 𝑋 𝑛𝑒𝑤 ;
	13:	else v← 𝑒 -(𝑓(𝑋 𝑛𝑒𝑤 )-𝑓(𝑋 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 )/𝑇
	14:	Randomly generate a number ε between 0 and 1
	15:	If 𝜀 < v, then 𝑋 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 ← 𝑋 𝑛𝑒𝑤 ; end if
	16:	end if
	17:	If f(𝑋 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 ) < f(𝑋 𝑏𝑒𝑠𝑡 ), then 𝑋 𝑏𝑒𝑠𝑡 ← 𝑋 𝑛𝑒𝑤 end if
	18:	T← ℎ𝑇
	after reaching the maximum number of iterations (Majidi, Hosseini-Motlagh and 19: Update the selection probability of each operator according to the adaptive
	Ignatius,2018). weight adjustment strategy
	20: end for
	7:	Select a remove operator d from D with the probability 𝑃 𝑑 𝑡
	8:	The remove operator d is applied to 𝑋 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 to obtain a partial solution
		X 𝑛𝑒𝑤 '	.
	9:	Select an insertion operator i from I with the probability 𝑃 𝑖 𝑡
	10:	The insertion operator i is applied to X 𝑛𝑒𝑤 '	to obtain a new feasible solution
		𝑋 𝑛𝑒𝑤
	11:	If f(𝑋 𝑛𝑒𝑤 )< f(𝑋 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 ), then

Algorithm 5.1 -Pseudo-code of ALNS metaheuristic 1: Generate an Initial Solution by Saving Algorithm (Section 5.3.2.1) 2: Initialize weight and score of each destroy operator d and each repair operator i; Where d∈ 𝐷, i∈ 𝐼. 3: Initialize constant 𝑃 𝑖𝑛𝑖𝑡 , cooling rate h, removal fraction 𝜌 4: 𝑋 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 ← 𝑋 𝑖𝑛𝑖𝑡 5: T← 𝑇 𝑏𝑒𝑔 6: for iter ←1 to niters do

Table 5 .

 5 1 Parameter Setting of the ALNS for different sizes of instances.

		Small	Medium	Large
	Parameter
		instances	instances	instances
	Maximum iterations number of ALNS (N)	25000	30000	35000
	The roulette parameter (r)	0.1	0.1	0.1
	The score increment of generating a new best solution (Q1) 5	5	5
	The score increment of generating a better solution (Q2)	3	3	3
	The score increment of generating a worse solution (Q3)	1	1	1
	Initial temperature parameter(𝑃 𝑖𝑛𝑖𝑡 )	100	120	120
	Cooling rate(h)	0.92	0.94	0.96
	Removal fraction (𝜌)	0.2	0.2	0.3
	Noise parameter(u)	0.1	0.1	0.1

Table 5 .2

 5 Performance indexes.

	Abbreviation	Definition
	𝐶𝑝𝑙𝑒𝑥

𝑂𝑏𝑗

The best feasible objective value found by CPLEX in a preset running time Chapter 5.

Route Planning of Freight Buses with both Pickup and Delivery

  The gap between 𝐴𝐿𝑁𝑆 𝑂𝑏𝑗 and LB, which is defined as (𝐴𝐿𝑁𝑆 𝑂𝑏𝑗 -LB)/ 𝐴𝐿𝑁𝑆 𝑂𝑏𝑗 *100𝐼𝑚𝑝 𝐴𝐿𝑁𝑆-𝐶𝑝𝑙𝑒𝑥The improvement (cost reduction) of 𝐴𝐿𝑁𝑆 𝑜𝑏𝑗 over 𝐶𝑝𝑙𝑒𝑥 𝑂𝑏𝑗 , which is defined as (𝐶𝑝𝑙𝑒𝑥 𝑂𝑏𝑗 -𝐴𝐿𝑁𝑆 𝑜𝑏𝑗 )/ 𝐴𝐿𝑁𝑆 𝑂𝑏𝑗 *100

	LB	The lower bound produced by CPLEX in a preset running time
		The best feasible objective value obtained by ALNS after a preset
	𝐴𝐿𝑁𝑆 𝑂𝑏𝑗
		number of iterations
	𝐺𝑎𝑝 𝐶𝑝𝑙𝑒𝑥	The gap between 𝐶𝑝𝑙𝑒𝑥 𝑂𝑏𝑗 and LB, which is defined as (𝐶𝑝𝑙𝑒𝑥 𝑂𝑏𝑗 -LB)/ 𝐶𝑝𝑙𝑒𝑥 𝑂𝑏𝑗 *100
	𝐺𝑎𝑝 𝐴𝐿𝑁𝑆
	𝐶𝑃𝑈 𝐶𝑝𝑙𝑒𝑥	The CPU time of CPLEX (in seconds)

Table 5 .3

 5 Experimental results of small size instances.

	Instances 𝐶𝑝𝑙𝑒𝑥 𝑂𝑏𝑗 LB	𝐴𝐿𝑁𝑆 𝑂𝑏𝑗 𝐺𝑎𝑝 𝐶𝑝𝑙𝑒𝑥 𝐺𝑎𝑝 𝐴𝐿𝑁𝑆 𝐼𝑚𝑝 𝐴𝐿𝑁𝑆-𝐶𝑝𝑙𝑒𝑥 𝐶𝑃𝑈 𝐶𝑝𝑙𝑒𝑥 𝐶𝑃𝑈 𝐴𝐿𝑁𝑆
	7-3a	1067.1	1067.1	1067.1	0.00	0.00	0.00	86.3	7.9
	7-3b	986.6	986.6	986.6	0.00	0.00	0.00	89.6	7.6
	7-3c	1076.9	1076.9	1076.9	0.00	0.00	0.00	87.9	8.2
	7-3d	962.0	962.0	962.0	0.00	0.00	0.00	87.6	8.7
	7-3e	1005.8	1005.8	1005.8	0.00	0.00	0.00	87.5	7.9
	7-5a	1984.1	1984.1	1984.1	0.00	0.00	0.00	257.3	19.7
	7-5b	1945.1	1945.1	1945.1	0.00	0.00	0.00	262.1	20.3
	7-5c	1887.0	1887.0	1887.0	0.00	0.00	0.00	258.2	21.9
	7-5d	1940.4	1940.4	1940.4	0.00	0.00	0.00	259.3	19.8
	7-5e	1896.6	1896.6	1896.6	0.00	0.00	0.00	260.3	20.3
	13-3a	1459.9	1074.8	1197.0	26.38	10.21 21.96	3600	25.8

Table 5 . 5 .

 55 Experimental results of large size instances.

	Instances 𝐶𝑝𝑙𝑒𝑥 𝑂𝑏𝑗	LB	𝐴𝐿𝑁𝑆 𝑂𝑏𝑗 𝐺𝑎𝑝 𝐶𝑝𝑙𝑒𝑥 𝐺𝑎𝑝 𝐴𝐿𝑁𝑆 𝐼𝑚𝑝 𝐴𝐿𝑁𝑆-𝐶𝑝𝑙𝑒𝑥 𝐶𝑃𝑈 𝐶𝑝𝑙𝑒𝑥 𝐶𝑃𝑈 𝐴𝐿𝑁𝑆
	60-3a	11510.5 4550.1	5313.7	60.47	14.37 116.62	979.3
	60-3b	-	5140.4	5971.6	-	13.92 -	1000.1
	60-3c	11918.4 4742.3	5507.3	60.21	13.89 116.41	1005.3
	60-3d	-	4340.2	5106.7	-	15.01 -	989.3
	60-3e	11509.7 4694.8	5494.9	59.21	14.56 109.46	996.1
	60-5a	-	8123.9	9972.9	-	18.54 -	1421.6
	60-5b	-	7669.4	9493.1	-	19.21 -	1432.3
	60-5c	-	8041.2	9809.9	-	18.03 -	1410.5
	60-5d	-	8318.1	10172.5 -	18.23 -	1396.3
	60-5e	-	8372.7	10135.2 -	17.39 -	1389.3
	80-3a	-	6288.6	7419.3	-	15.24 -	1523.4

Table 5 .

 5 3 reports the experimental results on the 20 small size instances. We can see, both ALNS and CPLEX can solve the model to optimality for the instances with N=7,

M=3 and N=7, M=5 . However, when the number of depot nodes increases to 13, no proven optima was obtained. Comparing their three indexes (𝐺𝑎𝑝 𝐶𝑝𝑙𝑒𝑥 , 𝐺𝑎𝑝 𝐴𝐿𝑁𝑆 and 𝐼𝑚𝑝 𝐴𝐿𝑁𝑆-𝐶𝑝𝑙𝑒𝑥 ), we can see that ALNS found better solutions than CPLEX with an average percentage improvement 𝐼𝑚𝑝 𝑀𝐴-𝐶𝑝𝑙𝑒𝑥 of 25.94% in terms of total cost. Furthermore, we can see our ALNS has a great advantage over CPLEX in terms of running time, the longest CPU time for ALNS is only 42.3 seconds compared with the limit of 3600 seconds reached by CPLEX.

Table 5 .

 5 4 compares the experimental results of the two solution methods for medium size instances. With the increase of the number of depot nodes, the gap of CPLEX

	𝐺𝑎𝑝 𝐶𝑝𝑙𝑒𝑥 , has a rapid growth from 31.82% to 55.67%, while our ALNS maintains a
	relatively smaller change from 6.67% to 19.92%. As a result, there is a significant
	increase in the improvement 𝐼𝑚𝑝 𝐴𝐿𝑁𝑆-𝐶𝑝𝑙𝑒𝑥 from 31.58% to 89.47%. For the instances
	with N=30, M=5 (30-5) , N=40, M=3 (40-3), and N=40, M=5 (40-5), we can see
	sometimes CPLEX failed to find a feasible solution, even after a long running of 2h or
	3h. By contrast, the performance of our ALNS still remains stable with only a fraction

of running time (average 476.68 seconds) of the CPLEX MILP solver.

Table 5 .

 5 5 summarized the results for 20 large size instances. We can see CPLEX achieved to find a feasible solution for only 3 out of 20 instances with a preset running time. For most of the instances, CPLEX stopped due to out of memory. In this case, we can only compare the lower bound LB produced by CPLEX and the upper bound found by the ALNS ( 𝐴𝐿𝑁𝑆 𝑂𝑏𝑗 ). For large size instances, we can see our ALNS produced solutions with an average gap 𝐺𝑎𝑝 𝐴𝐿𝑁𝑆 of 17.04%, and the best improvement 𝐼𝑚𝑝 𝐴𝐿𝑁𝑆-𝐶𝑝𝑙𝑒𝑥 of the ALNS over CPLEX could reach 116.62%. The average performances of the two solution methods.

	Table 5.6 Instances	𝐺𝑎𝑝 𝐶𝑝𝑙𝑒𝑥 𝐺𝑎𝑝 𝐴𝐿𝑁𝑆 𝐼𝑚𝑝 𝐴𝐿𝑁𝑆-𝐶𝑝𝑙𝑒𝑥 𝐶𝑃𝑈 𝐶𝑝𝑙𝑒𝑥 𝐶𝑃𝑈 𝐴𝐿𝑁𝑆
	7-3	0	0	0	87.78	8.06
	7-5	0	0	0	259.44	20.4
	13-3	28.76	10.81	25.54	3600	26.3
	13-5	31.80	13.93	26.35	3600	40.76
	20-3	31.82	8.72	33.88	5400	135.9
	20-5	42.81	11.79	54.25	5400	211.7
	30-3	46.44	11.97	64.38	7200	289.1
	30-5	49.83	16.11	67.51	7200	354.5
	40-3	53.50	16.06	80.90	10800	475.1
	40-5	-	19.30	-	10800	600.4
	60-3	59.96	14.35	114.16	14400	994.0
	60-5	-	18.28	-	14400	1410.0
	80-3	-	15.78	-	18000	1543.8
	80-5	-	19.75	-	18000	1983.4

Table 5 .

 5 7. The comparison of the average costs of the two systems.

		Instances	System without	System with	Cost Saving in
			Freight bus	Freight bus	percentage
	Small size	7-3	1237.50	1019.7	17.6
	instances	7-5	2363.04	1930.6	18.3
		13-3	1779.70	1429.1	19.7
		13-5	3400.00	2713.2	20.2
	Medium size	20-3	2818.08	2167.1	23.1
	instances	20-5	3938.60	3040.6	22.8
		30-3	3909.40	2951.6	24.5
		30-5	6635.24	4989.7	24.8
		40-3	4625.98	3437.1	25.7
		40-5	8168.02	6028.0	26.2
	Large size	60-3	7749.36	5478.8	29.3
	instances	60-5	14186.98	9916.7	30.1
		80-3	10945.48	7267.8	33.6
		80-5	16565.84	10718.1	35.3

Table 6 .

 6 2. Results of small size instances. Instances 𝐶𝑝𝑙𝑒𝑥 𝑂𝑏𝑗 LB 𝐴𝐼𝐴 𝑂𝑏𝑗 𝐺𝑎𝑝 𝐶𝑝𝑙𝑒𝑥 𝐺𝑎𝑝 𝐼𝐺𝐴 𝐼𝑚𝑝 𝐼𝐺𝐴-𝐶𝑝𝑙𝑒𝑥 𝐶𝑃𝑈 𝐶𝑝𝑙𝑒𝑥 𝐶𝑃𝑈 𝐼𝐺𝐴

	7-3	987.0	987.0	987.0	0	0	0.00	2908.8	98.6

Table 6 .4.

 6 Results of large size instances. Instances 𝐶𝑝𝑙𝑒𝑥 𝑂𝑏𝑗 LB 𝐴𝐼𝐴 𝑂𝑏𝑗 𝐺𝑎𝑝 𝐶𝑝𝑙𝑒𝑥 𝐺𝑎𝑝 𝐼𝐺𝐴 𝐼𝑚𝑝 𝐼𝐺𝐴-𝐶𝑝𝑙𝑒𝑥 𝐶𝑃𝑈 𝐶𝑝𝑙𝑒𝑥 𝐶𝑃𝑈 𝐼𝐺𝐴Table 6.2 compares the solutions obtained by our Immune Genetic algorithm with that obtained by CPLEX solver on small size instances. We can see, for the instance with N=7 and M=3, both IGA and CPLEX can solve the MILP model to optimality.

	60-3	-	4686.0	5527.2	-	15.22	-	32400.0	7269.8
	60-5	-	8349.5	9974.3	-	16.29	-	32400.0	9708.1
	80-3	-	5871.5	7428.5	-	20.96	-	36000.0 11071.3
	80-5	-	9631.3 11798.7	-	18.37	-	36000.0 15060.3

Table 6 .5

 6 Comparison of the performances of IGA and GA.

			IGA	𝐺𝐴
	Instance sets					𝐼𝑚𝑝 𝐼𝐺𝐴	∆ cpu
		CostIGA	CPUIGA	CostGA	CPUGA
	7-3	987.0	98.6	987.0	98.1	0.00	0.51
	7-5	1931.3	198.5	1931.3	197.1	0.00	0.71
	13-3	1483.8	241.6	1499.5	239.5	1.06	0.87
	13-5	2742.4	368.3	2776.0	365.7	1.23	0.71
	20-3	2109.1	920.4	2148.4	907.8	1.86	1.37
	20-5	3154.6	1345.6	3284.0	1333.7	4.10	0.88
	30-3	3014.7	1462.9	3099.3	1441.8	2.81	1.44
	30-5	5041.6	2089.7	5274.2	2070.4	4.61	0.92
	40-3	3538.4	2073.2	3720.3	2040.8	5.14	1.56
	40-5	6019.3	2696.7	6314.2	2671.1	4.90	0.95
	60-3	5527.2	7269.8	5815.0	7156.7	5.21	1.56
	60-5	9974.3	9708.1	10579.4	9616.7	6.07	0.94
	80-3	7428.5	11071.3	7904.3	10915.2	6.41	1.41
	80-5	11798.7	15060.3	12539.8	14796.9	6.28	1.75

  Tout comme les bus de passagers, les bus de fret peuvent être gérés par la mairie, et fournir un service public pour la logistique de la ville. Du fait de leur utilisation partagée par tous les fournisseurs qui souhaitent livrer ses marchandises à leurs clients, on peut s'attendre à ce que les bus de fret présentent certains avantages par rapport aux cargos urbains: Premièrement, les bus de fret peuvent assurer la distribution conjointe de différentes entreprises de logistique tierces, ce qui permet de réduire les coûts de logistique urbaine et de réduire la pollution atmosphérique; Deuxièmement, grâce à un horaire régulier, les bus de fret peuvent améliorer la rapidité et la précision des services logistiques; Troisièmement, le remplacement des cargos urbains privés par des bus de fret peut faciliter le contrôle du trafic dans une ville et réduire les embouteillages. Enfin, les bus de fret peuvent améliorer le taux d'utilisation des voies spéciales réservées aux bus.Le transport routier par véhicule est la partie la plus importante de nombreux systèmes logistiques, et l'optimisation de l'itinéraire des véhicules a été un sujet de recherche d'actualité pour de nombreux chercheurs dans le domaine de la recherche opérationnelle et de la science de la gestion dans le monde entier. Dans cette thèse, nous étudions également le problème de la planification de l'itinéraire des bus de fret dans un système de distribution urbain. Dans le problème, chaque bus de fret a un itinéraire fixe, il effectue à plusieurs reprises un circuit partant d'un centre de distribution (CD), de la recherche et la signification du travail de cette thèse, ainsi que le contenu principal et l'organisation de cette thèse. Le chapitre 2 donne une synthèse de la littérature des travaux de recherche liés à cette thèse, résume une classification des problèmes de tournées de véhicules étudiés dans la litérature, et décrit les principaux algorithmes pour résoudre les problèmes de tournées de véhicules. Le chapitre 3 présente le concept de bus de fret, et décrit l'infrastructure ainsi que le mode de fonctionnement du système de distribution de bus de fret. Les trois chapitres suivants sont consacrés à l'étude du problème de planification d'itinéraires de bus de fret : Les chapitres 4 et 5 étudient le problème de planification d'itinéraires de bus de fret avec demandes déterministes. Le problème de base de la planification d' itinéraires des bus de fret avec seulement des demandes de livraison est étudié au chapitre 4, et le chapitre 5 étudie le problème de tournées de bus de fret avec ramassages et livraisons; Le chapitre 6 étudie le problème d'itinéraires de bus de fret avec demandes stochastiques. Le chapitre 7 résume les travaux de cette thèse et indique la recherche future pour la mise en place de buses de fret. Le VRP a été introduit par Dantzig et Ramser en 1959 comme une extension du TSP. Les TSP et les VRP, appartenant aux problèmes classiques d'optimisation combinatoire, ont de nombreuses applications dans la vie courante, notamment le problème de la route des véhicules dans le secteur de la livraison express, le secours médical, le dédouanement des déchets, la planification des équipements logistiques des ateliers de fabrication, le problème de la livraison postale, etc. Pour cette raison, ils ont attiré l'intérêt de nombreux experts et chercheurs en matière de recherche. Les recherches sur la tournée des véhicules concernent la gestion, les sciences de la logistique, la recherche opérationnelle, les mathématiques, les applications informatiques, la théorie des graphes et d'autres disciplines. De grandes variantes de VRP ont été proposées et étudiées dans la littérature. La plupart d'entre elles se sont avérées NP-difficiles, ce qui est très difficile à résoudre. Les chercheurs ont proposé des algorithmes exacts

	French Abstract
	. Les conséquences probables de cette expansion sont d'augmentation des embouteillages du trafic, de pollution atmosphère et sonore, mais également une grande base de clients et des opportunités commerciales plus importantes en raison des économies d'échelle. Déplacer les cargos entre les villes et à l'intérieur des villes tout en préservant la qualité de vie des résidents est un défi majeur pour les urbanistes et les prestataires des services logistiques. À travers un grand nombre de littérature scientifique et d'observations industrielles, nous pouvons constater que les principaux problèmes auxquels la logistique urbaine est actuellement confrontée sont les suivants: Premièrement, l'infrastructure de la logistique urbaine a besoin de mise à jour et d'être transformée. Deuxièmement, la qualité et l'efficacité du service du 'dernier kilomètre' dans la logistique urbaine a besoin d'améliorer. Troisièmement, diverses entreprises de logistique manquent encore de coopération. Quatrièmement, la logistique urbaine a besoin d'améliorer son propre niveau de mécanisation et d'informatisation. Cinquièmement, le gouvernement a besoin de mettre en place une planification et une gestion unifiées pour un développement sain de la logistique urbaine. Motivés par la distribution conjointe, nous avons présenté pour la première fois dans cette thèse le concept de bus de fret, un nouveau moyen de transport en commun pour la logistique urbaine qui peut remplacer les cargos urbains appartenant à des différentes entreprises de logistique tierces privées situées au centre d'une métropole système sont visités par plusieurs bus de fret avec la même fréquence de visite. Le problème de planification d'itinéraire peut être considéré comme une nouvelle variante du Problème de tournées périodique des véhicules. Pour autant que nous sachions, les bus dédiés au transport de fret ont rarement été abordés dans la littérature et le problème de tournées du fret dans ce thèse n'a jamais été étudié par d'autres chercheurs. Nous avons étudié trois variantes du problème de planification d'itinéraires de bus de fret : le problème de base avec demandes de livraison uniquement, le problème avec ramassages et livraisons, et le problème avec demandes de ramassage et de livraison stochastiques. Pour chaque variante du problème, après avoir établi un modèle mathématique, nous avons développé un algorithme métaheuristique pour la résoudre. un système de bus de fret comme moyen de distribution de fret urbain, et étudie le problème de la planification d'itinéraires des bus de fret dans circonstances différentes. Cette recherche a une signification pratique et théorique. 1) Du point de vue d'application, l'introduction de bus de fret offre de nouvelles possibilités à la mairie et aux entreprises de logistiques d'améliorer les services logistiques fournis aux fournisseurs (fabricants) et aux clients, tout en réduisant les coûts de logistique et l'impact négatif de la distribution de fret urbain sur l'environnement. 2) Deuxièmement, du point de vue des entreprises de logistique, tout d'abord, le bus de fret est un nouveau type de système de transport collaboratif pour les entreprises souligné que les émissions d'oxydes d'azote et de particules en suspension provenant du transport de marchandises dans les villes représentaient 40% et 45% des émissions totales des transports urbains. Par conséquent, grâce au transport collaboratif et à l'optimisation des itinéraires des buses de fret, il est possible de réduire le nombre de trajets, le kilométrage et le taux de chargement à vide des véhicules tout en répondant aux besoins des clients, et enfin de réduire les embouteillages, les nuisances sonores et les émissions de gaz d'échappement. 5) Du point de vue de la recherche, le problème de la planification d'itinéraires des bus de fret est un nouveau problème de tournées périodique des véhicules. Dans cette thèse, nous avons étudié trois variantes du problème de planification d'itinéraires de comme Pékin et Paris. se rendant à plusieurs dépôts et revenant au centre de distribution. Tous les dépôts du bus de fret contribuera à améliorer le niveau de service du système logistique et à promouvoir davantage le développement de ces entreprises. 3) Troisièmement, du point de vue du client, grâce à un horaire régulier, l'utilisation des bus de fret peut améliorer la rapidité et la précision des services logistiques. Le transfert en douceur des marchandises du fournisseur au client est la condition sine qua non pour assurer le fonctionnement normal de la vie du client. Dans l'environnement du commerce électronique, si les marchandises achetées par le client ne lui sont pas livrées à temps, cela peut affecter la vie normale du client et causer son mécontentement à l'égard de l'entreprise de commerce électronique et de l'entreprise de livraison express. Chaque bus de transport de fret sera exploité périodiquement et a un horaire opérationnel régulier pour s'assurer que les marchandises seront livrées aux clients à temps, ce qui améliorera considérablement le niveau de service pour les clients. 4) Quatrièmement, du point de vue de l'environnement urbain, un excellent système de distribution est propice à la réduction de la circulation dense dans la ville, à la réduction de la pollution sonore et atmosphère de la ville. Segalou et al. (2004) ont principalement le contexte Accompagnée du développement de la logistique urbaine, cette thèse met en avant pour les fournisseurs et les entreprises de commerce électronique, la recherche sur les A.2 Synthèse de littérature
	Le choix de chaque algorithme prend en compte les caractéristiques de la variante de logistique. Le transport collaboratif des bus de fret peut aider les entreprises de bus de fret : le problème de base avec demandes de livraison uniquement, le problème
	correspondante du problème étudiée. La pertinence des modèles et l'efficacité des logistique à résoudre le problème du «dernier kilomètre» pour la distribution urbaine avec ramassages et livraisons, et le problème avec demandes de ramassage et de
	algorithmes proposés sont prouvées par des expérimentations numériques intensives. afin d'aider davantage les entreprises de logistique à améliorer l'efficacité du travail, à livraison stochastiques. Les résultats de recherche de cette thèse enrichissent la
	Ce mémoire de thèse comprend un total de 7 chapitres. Le chapitre 1 présente réduire les coûts de distribution et à réaliser des profits plus importants. Deuxièmement, littérature sur le problème de tournées de véhicules.
	123

4 Modèle et algorithme pour la planification d'itinéraire des bus de fret avec livraisons seulement A.4.1 Description du problème

  Une caractéristique importante des bus de fret est qu'ils sont des véhicules standardisés et qu'ils ont des itinéraires et des horaires fixes. Comme les bus de passagers, un itinéraire de véhicule fixe pour chaque bus de fret peut ne pas être le plus économique en termes de coût, De manière plus précise, le bus de fret peut être défini comme: le fret est un véhicule public circulant dans une ville et fournissant des services de logistique urbaine. Comme un bus de passagers, chaque bus de fret a un itinéraire et un horaire fixe et peut utiliser des voies spéciales réservées aux bus.Dans le modèle, les bus de fret acheminent les marchandises d'un centre de distribution à un ensemble de dépôts. Pour des raisons de simplicité, nous n'envisageons pas les interactions des bus de fret avec les tricycles électriques qui effectuent les livraisons du dernier kilomètre des dépôts aux clients. Nous divisons l'horizon temporel de planification (par exemple, un jour) des opérations des bus de fret en M périodes (M> 1). En tant que étude 1 du problème d' itinéraires des bus de fret, nous supposons que la demande à chaque dépôt est connue. Cette demande peut être prévue à l'avance tous les jours ou peut être estimée par la moyenne des demandes historiques du dépôt pour la même période et le même jour de chaque semaine pendant un an, un trimestre ou un mois. De plus, nous supposons que chaque bus de fret a un itinéraire fixe dans l'horizon temporel et que chaque dépôt doit être desservi par un bus de fret à chaque période. La demande totale de livraison de chaque dépôt doit être satisfaite à la fin de l'horizon temporel, mais il est possible que la demande d'un dépôt

mais avec les itinéraires et les horaires fixes, les bus de fret peuvent fournir un service stable et précis, et les expéditeurs et les clients peuvent organiser les délais de livraison de leurs commandes. Chaque dépôt dans ce système de distribution est une station de bus de fret, qui peut être une armoire intelligente (dépôt) pour le stockage temporaire de marchandises. Selon les horaires, les clients peuvent retirer leurs produits commandés en libre-service dans les stations de bus (dépôts) pour le transport de marchandises (dépôts) ou demander aux livreurs du dernier kilomètre de livrer les marchandises d'une station de bus à leur domicile

[START_REF] Taniguchi | An Evaluation Methodology for Urban logistics[END_REF]

.

A.

au cours d'une période donnée ne soit que partiellement satisfaite au cours de cette période en raison de la capacité limitée d'un bus de fret. Dans ce cas, la demande non satisfaite de la période sera satisfaite au cours de périodes ultérieures, mais avec une pénalité pour livraison tardive dépend linéairement en fonction de la quantité de retard et du nombre de périodes retardées. En raison de la pénalité de retard de livraison, toutes les demandes doivent être satisfaites au plus tôt possible.

  Nous supposons que le centre de distribution dessert tous les dépôts G du système de distribution considéré. La distance entre le noeud i et le noeud j est notée 𝐷 𝑖𝑗 . Chaque bus de fret charge les marchandises au centre de distribution, les livre à un sousensemble de dépôts et les ramène enfin au centre de distribution. Le coût d'exploitation d'un bus de fret du noeud i au noeud j est calculé comme suit: 𝐶 𝑖𝑗 = 𝐶 * 𝐷 𝑖𝑗 , où C est le coût d'exploitation unitaire à la distance de chaque bus de fret. Il existe F (F est un nombre entier) de bus de fret exploités pour le centre de distribution o, et la capacité de chaque bus de fret est de U.A chaque période, chaque bus de fret part du centre de distribution o, se rend dans ses dépôts desservis et retourne au centre de distribution. De plus, chaque période, toutes les marchandises doivent être déchargées de l'bus de fret avant de revenir au centre de distribution. On suppose que la demande 𝑑 Quantité non chargée de l'bus de fret v ϵV au dépôt i ϵG lors de la k-ème visite

	raison de la pénalité de retard de livraison, toutes les demandes doivent être satisfaites
	le plus tôt possible.
		Le modèle mathématique détaillé pour la planification d'itinéraire des bus de fret
	est donné comme suit:
	Variables de décision
	x 𝑖𝑗 v	Une variable binaire égale à 1 si le bus de fret v ϵV passe du noeud i à j (i, jϵ {o}
	∪G); 0 sinon.
	y 𝑖 v Une variable binaire égale à 1 si et seulement si le dépôt i ϵG est desservi par le
	bus cargo v ϵV; 0 sinon.
	𝑑 𝑖 𝑣 (k) k∈ {1,2… m}; 0 sinon.
	Fonction objectif :
		L'objectif est de minimiser la somme des coûts, qui comprennent les coûts
	d'exploitation des bus de fret et les coûts des pénalités pour retard de livraison dans
	l'horizon de planification des M périodes.
	A.4.2 Modèle mathématique Min Obj = 𝑀 * ∑	𝑖∈{𝑜}∪𝐺	∑ 𝑗∈{0}∪𝐺	∑ 𝑐 𝑖𝑗 𝑥 𝑖𝑗 𝑣 𝑣∈𝑉
		Comme nous pouvions observer de la description du problème, il existe trois
	caractéristiques importantes pour la planification d'itinéraire des bus de fret avec
	livraisons seulement: Premièrement, chaque bus de fret a un itinéraire fixe dans
	l'horizon temporel, et chaque dépôt doit être desservi par un bus de fret à chaque période;
	Deuxièmement, la demande d'un dépôt à chaque période peut être divisée en une
	demande livrée à temps dans cette période et une demande livrée à des périodes
	ultérieures en raison de la capacité limitée d'un bus de fret en cause. Troisièmement, en

• P Coefficient de pénalité (par période et par unité de demande) pour le retard de livraison. 𝑖 (𝑘) de chaque dépôt i à chaque période k∈ {1,2… M} est connue. Dans chaque période, la livraison de bus de fret v à chaque dépôt i peut être la demande de cette période plus la demande (la demande partielle) des périodes précédentes, mais ne peut pas être la demande d'une période ultérieure.

Nous devons planifier le parcours des véhicules pour chaque bus de fret v et la quantité de livraison de chaque bus de fret à chaque dépôt à chaque période. Notre objectif est de minimiser les coûts d'exploitation de tous les bus de fret, ainsi que les pénalités de retard de livraison pour les périodes M.

𝑄 𝑖

𝑣 (k) Charge du bus de fret v ϵV lorsqu'il vient d'arriver au noeud i ϵ {o}∪G lors de la k-ième visite, k∈ {1,2… M}.

5 Modèle et algorithme pour la planification d'itinéraire des bus de fret avec ramassages et livraisons A.5.1 Description du problème

  En particulier, notre développement de cet algorithme prend en compte les caractéristiques spécifiques de ce problème, telles que l'itinéraire fixe pour chaque bus de fret, la demande peut être servie plus tard, mais avec un coût de pénalité de livraison tardive, etc. Méthodes pour coder / décoder, calculer l'adéquation de chaque solution, pour effectuer une recherche locale dans l'algorithme. 𝐺𝑎𝑝 𝑀𝐴 et 𝐼𝑚𝑝 𝑀𝐴-𝐶𝑝𝑙𝑒𝑥 ), nous pouvons constater que MA a trouvé de meilleures solutions que CPLEX avec un pourcentage moyen d'amélioration 𝐼𝑚𝑝 𝑀𝐴-𝐶𝑝𝑙𝑒𝑥 de 19.31% en termes de coût total. De plus, nous constatons que notre MA a un grand avantage sur CPLEX en termes de temps d'exécution. Le temps de calcul le plus long pour MA est de seulement 37,2 secondes par rapport à la limite de 1800 secondes atteinte par CPLEX. Pour les instances de taille moyenne, en revanche, notre MA pourrait toujours trouver de meilleures solutions réalisables. Bien que le temps d'exécution de l'agent de gestion augmente de 98,5 secondes à 550,7 secondes, son temps de calcul est bien inférieur à celui de CPLEX dans toutes les instances. Pour les instances de grande taille, nous pouvons voir que nos solutions élaborées par MA ont un écart moyen 𝐺𝑎𝑝 𝑀𝐴 de 14,44% et que la meilleure amélioration B de l'EM par rapport à CPLEX pourrait atteindre 119,11%. Ces résultats expérimentaux montrent que notre algorithme memetic est efficace pour résoudre le problème de la plannification d'itinéraires de bus de fret étudié dans cette thèse.Au chapitre 5, le thèse fait de la recherche supplémentaire sur le problème de l'itinéraire de bus de fret sur la base du chapitre 4. Étant donné qu'en pratique, en tant que nouveau moyen de transport en commun pour la logistique urbaine, les bus de fret doivent effectuer le ramassage et la livraison des marchandises sur chaque site client / fournisseur visité. Dans ce chapitre, nous étudions le problème de la planification d'itinéraire de bus de fret avec ramassage et livraison dans un système de distribution bus de fret avec les tricycles électriques qui effectuent les livraisons du dernier kilomètre des dépôts aux clients. Les principales caractéristiques du modèle sont d'abord présentées dans ce qui suit.

					∀k∈ {1,2 … M}	(4.5)
	𝑄 𝑜 𝑣 (𝑘) = 0		∀𝑣 ∈ 𝑉, ∀k∈ {1,2 … 𝑀}	(4.6)
	0<= 𝑄 𝑖 𝑣 (𝑘)<=U		∀𝑖 ∈ 𝐺, ∀𝑣 ∈ 𝑉	(4.7)
	∑ 𝑀 𝑘=1	𝑑 𝑖 𝑣 (𝑘)	= 𝑑 𝑖 *𝑦 𝑖 𝑣		∀𝑖 ∈ 𝐺, ∀𝑣 ∈ 𝑉	(4.8)
	∑ 𝑛 𝑘=1	𝑑 𝑖 𝑣 (𝑘)	<= ∑ 𝑛 𝑘=1	𝑑 𝑖 (𝑘)	*𝑦 𝑖 𝑣
	∀𝑖 ∈ 𝐺, ∀𝑣 ∈ 𝑉, ∀n∈ {1,2 … 𝑀}	(4.9)
	𝑥 𝑖𝑗 𝑣 ∈ {0,1} 𝑦 𝑖 𝑣 ∈ {0,1}
	∀𝑖 ∈ {𝑜} ∪ 𝐺,∀𝑗 ∈ {𝑜} ∪ 𝐺, ∀𝑣 ∈ 𝑉	(4.10)
	Les contraintes (4.1) indiquent que chaque bus de fret part et revient au centre de
	distribution. Les contraintes (4.2) garantissent que chaque bus de fret arrivant à un urbain.
	dépôt doit le quitter. Les contraintes (4.3) et (4.4) garantissent que tous les dépôts Comme le chapitre 4, le problème est décrit en premier lieu, chaque bus de fret peut
	doivent être desservis et que chaque dépôt est desservi par au plus un bus de fret. Les effectuer le ramassage et la livraison des marchandises à chaque dépôt (emplacement
	contraintes (4.5) (4.6) et (4.7) définissent les contraintes de capacité des véhicules. Les client / fournisseur). Le bus de fret arrive à chaque emplacement client / fournisseur
	contraintes (4.8) garantissent que toutes les demandes de chaque dépôt doivent être (gare), décharge les marchandises en premier et charge les marchandises plus tard.
	satisfaites dans l'horizon temporel de M périodes. Les contraintes (4.9) indiquent que, Pendant toute la durée du voyage, la quantité totale de marchandises dans le bus ne doit
	pour chaque période, la livraison de bus de fret v à chaque dépôt i peut correspondre à pas dépasser sa capacité. L'objectif est de minimiser les coûts d'exploitation de tous les
	la demande de cette période ou de périodes antérieures, mais ne peut pas être à la bus de fret, ainsi que les frais de retard de livraison et de ramassage. Afin de résoudre
	demande de périodes ultérieures. Enfin, les contraintes (4.10) définissent les domaines ce problème, un modèle MILP (Mixed-Integer Linear Programming) est formulé et un
	de toutes les variables de décision. algorithme ALNS (Algorithme de recherche adaptative à grand voisinage) est
	développé en combinaison avec les caractéristiques du problème, la validité du modèle
	et l'efficacité de notre algorithme ALNS est vérifié par des expérimentations
	numériques.

A.4.3 Algorithme mémétique

Dans ce chapitre, nous concevons un algorithme mémétique (algorithme génétique avec recherche locale) pour résoudre ce problème particulier de tournée périodique des véhicules. Basé sur les étapes conventionnelles des algorithmes génétiques, le cadre de procédure de notre algorithme Mémétique est illustré à la Fig.4.1 Fig.4.1 Algorithme Memetique Nous concevons 70 instances de tailles petite, moyenne et grande et comparons les performances de l'algorithme mémétique (implémenté dans MATLAB) avec celles du solveur CPLEX MILP sur les instances. Pour les petites instances, en comparant leurs trois indicateurs (index 𝐺𝑎𝑝 𝐶𝑝𝑙𝑒𝑥 , A.Dans le modèle, chaque bus de fret circule entre un centre de distribution et un ensemble de dépôts. Pour des raisons de simplicité, nous n'envisageons pas les interactions des

  Pénalité de retard de livraison / ramassage. La livraison et le ramassage des marchandises chez un client ou un fournisseur peuvent être en retard, mais avec des pénalités. Deux types de pénalités sont introduits dans ce modèle. L'une est la pénalité causée par le retard dans l'horizon temporel (par exemple, un jour) de M périodes, qui dépend linéairement de la quantité des demandes de livraison ou de ramassage tardives et du nombre de périodes retardées avec la pénalité par période et par unité de temps. demande donnée par un coefficient α (dans cet article, nous supposons que le ramassage et la livraison tardifs ont le même coefficient de pénalité). L'autre est la pénalité pour toutes les demandes non satisfaites à la fin de l'horizon temporel (par exemple un jour) de M périodes, qui dépend linéairement de la quantité des demandes de livraison ou de ramassage tardives, avec la pénalité par unité de demande donnée par un autre coefficient. β.De plus, à cause de ces deux types de pénalités, nous pouvons supposer que le fonctionnement du bus de fret a deux caractéristiques: 1, lorsque le bus de fret arrive à un dépôt, il décharge / livre en premier lieu, puis charge / ramasse les marchandises.(Afin de libérer plus de capacité de ramassage). 2, pour la livraison, le bus de fret donnera la priorité à la satisfaction des besoins des dépôts de visite précédents en fonction de l'ordre de visite; lors du ramassage, l'bus de fret fera de son mieux pour répondre aux besoins de chargement des dépôts en fonction de sa capacité restante maximale (car le ramassage et la livraison tardifs ont le même coefficient de pénalité). Quantité non chargée de l'bus de fret v ϵV au dépôt i ϵG lors de la k-ème visite La quantité de charge du bus de fret v ϵV au dépôt i ϵG lors de la k-ème visite La quantité de toutes les marchandises récupérées par le bus de fret v ϵV quand il vient d'arriver au noeud i ϵ{o}∪G lors de la k-ème visite, k∈ {1,2… M}.

	𝑑 𝑖 𝑣 (k)
	k∈ {1,2… m}; 0 sinon.
	𝑝 𝑖 𝑣 (k)
	k∈ {1,2… m}; 0 sinon.
	𝑄 𝑖 𝑣 (k)	La quantité de toutes les marchandises restant à livrer dans le bus de cargo v
	ϵV quand il vient d'arriver au noeud i ϵ {o} ∪G pendant la k-ième visite, k∈ {1,2…
	M}.
	𝑊 𝑖 𝑣 (k) Fonction objectif :
	A.5.2 Modèle mathématique
	Dans cette sous-section, nous proposons un modèle mathématique pour la Min Obj = 𝑀 * ∑ ∑ ∑ 𝑐 𝑖𝑗 𝑥 𝑖𝑗 𝑣 𝑣∈𝑉 𝑗∈{0}∪𝐺 𝑖∈{𝑜}∪𝐺 +
	planification de l'itinéraire des bus de fret en prenant en compte toutes ses
	caractéristiques. Avec ce modèle mathématique, nous pouvons optimiser le coût total 𝛼 * ∑ ∑ (∑ 𝑑 𝑖 (𝑘) 𝑛 𝑘=1 -∑ ∑ 𝑑 𝑖 𝑣 (𝑘) 𝑛 𝑘=1 𝑣𝜖𝑉 ) 𝑀-1 𝑛=1 𝑖∈𝐺 +
	des bus de fret composés de leurs coûts d'exploitation et des frais de pénalité pour retard 𝛽 *∑ ( ∑ 𝑑 𝑖 (𝑘) 𝑀 𝑘=1 -∑ ∑ 𝑑 𝑖 𝑣 (𝑘) 𝑀 𝑘=1
	de livraison et de ramassage des marchandises dans l'horizon de planification. En
	même temps, nous pouvons également obtenir les itinéraires optimaux des bus de fret
	en résolvant le modèle.
	Le modèle mathématique détaillé pour la planification d'itinéraire des bus de fret
	est donné comme suit:
	Variables de décision :
	𝑥 𝑖𝑗 𝑣	Une variable binaire égale à 1 si le bus de fret v ϵV passe du noeud i à j (i, jϵ
	{o}∪G); 0 sinon.
	𝑦 𝑖

) Livraison et enlèvement: chaque bus de fret peut effectuer l'enlèvement et la livraison des marchandises à chaque dépôt (emplacement client / fournisseur). Le bus de fret arrive à chaque emplacement client / fournisseur (gare), décharge les marchandises en premier et charge les marchandises plus tard. Pendant toute la durée du voyage, la quantité totale de marchandises dans le bus ne doit pas dépasser sa capacité. Il est donc possible que la livraison ou la demande de ramassage d'un dépôt au cours d'une période donnée ne soit que partiellement satisfaite au cours de cette période en raison de la capacité limitée d'un bus de fret. Dans ce cas, la demande non satisfaite de la période ne peut être satisfaite que ultérieurement.. En d'autres termes, les marchandises chargées ou déchargées par l'bus de fret doivent correspondre aux demandes de ramassage ou de livraison de cette période ou des périodes précédentes qui n'étaient pas satisfaites en raison de la limitation de la capacité du véhicule. (4) 𝑣 Une variable binaire égale à 1 si et seulement si le dépôt i ϵG est desservi par le bus cargo v ϵV; 0 sinon. L'objectif est de minimiser les coûts totaux, y compris les coûts d'exploitation des bus de fret et les pénalités liées aux retards de livraison et de ramassage des marchandises dans l'horizon de planification des M périodes.

  Si la nouvelle solution générée est acceptée, la solution actuelle sera mise à jour pour la prochaine itération. ALNS a été appliqué avec succès pour résoudre divers problème de tournées des véhicules

	variables de décision.
	A.5.3 Algorithme de recherche adaptative à grand voisinage (ALNS)
	L'algorithme de recherche de voisinage à grande échelle a été proposé pour la
	première fois par Shaw (1998). Ceci est un algorithme itératif. L'idée de l'algorithme
	est d'améliorer la solution actuelle à chaque itération en utilisant un opérateur de
	destruction qui supprime certains noeuds clients des itinéraires actuels et un opérateur
	de réparation qui réinsère ces noeuds clients dans les itinéraires. Si la nouvelle solution
	est meilleure que la solution actuelle, celle-ci est acceptée comme solution actuelle pour
	la prochaine itération.
						∀v ∈ 𝑉	(5.10)
	∑ 𝑛 𝑘=1	𝑑 𝑖 𝑣 (𝑘)	<= ∑ 𝑛 𝑘=1	𝑑 𝑖 (𝑘)	*𝑦 𝑖 𝑣
	∀𝑖 ∈ 𝐺, ∀𝑣 ∈ 𝑉, ∀n∈ {1,2 … 𝑀}	(5.11)
	∑ p 𝑖 v (k) n k=1	<= ∑ p 𝑖 (k) n k=1	*y 𝑖 v
	∀𝑖 ∈ G, ∀v ∈ 𝑉, ∀n∈ {1,2 … M}	(5.12)
	𝑥 𝑖𝑗 𝑣 ∈ {0,1} 𝑦 𝑖 𝑣 ∈ {0,1}
	𝑑 𝑖 𝑣 (𝑘)>=0 ; p 𝑖 (k)>=0 ; Q 𝑖 v (𝑘)>=0 ; W 𝑖 v (𝑘)>=0
	∀𝑖 ∈ {𝑜} ∪ 𝐺,∀𝑗 ∈ {𝑜} ∪ 𝐺, ∀𝑣 ∈ 𝑉	(5.13)
	Les contraintes (5.2) indiquent que chaque bus de fret part et revient au centre de
	distribution. Des contraintes (5.3) garantissent que chaque bus de fret arrivant à un
	dépôt doit le quitter. Les contraintes (5.4) et (5.5) garantissent que tous les dépôts
	doivent être desservis et que chaque dépôt est desservi par au plus un bus de fret. Les
	contraintes (5.6) (5.7) et (5.8) (5.9) (5.10) définissent les contraintes de capacité des
	véhicules. Les contraintes (5.11) (5.12) indiquent que pour chaque période, la livraison
	et le ramassage des bus de fret v à chaque dépôt i ne peuvent être que la demande de
	cette période ou de périodes antérieures, mais ne peuvent pas être la demande de
	périodes ultérieures. Enfin, les contraintes (5.13) définissent les domaines de toutes les

ALNS utilise plusieurs opérateurs de destruction et de réparation pour améliorer la solution actuelle à chaque itération. Le voisinage d'une solution peut être obtenu en supprimant plusieurs noeuds client des itinéraires actuels (solution) et en réinsérant les noeuds client. Dans ALNS, un opérateur de suppression et un opérateur de réinsertion sont sélectionnés de manière dynamique à chaque itération en fonction de leurs performances passées

[START_REF] Lv | An iterative algorithm for periodic Sylvester matrix equations[END_REF]

; chaque opérateur est associé à une probabilité. Si l'opérateur améliore la solution actuelle, la probabilité augmente, sinon la probabilité peut diminuer. La solution nouvellement générée est acceptée si elle améliore la solution actuelle, sinon elle sera acceptée avec une probabilité dépendant de la température et définie selon une règle de recuit par simulation (SA), la température sera progressivement diminuée avec la progression de l'algorithme;

Acknowledgments

This work has been carried out within Laboratory of Industrial Systems Optimization (LOSI) at University of Technology of Troyes (UTT). It is funded by

Generation of initial antibodies

In order to ensure the diversity of antibodies, we generate the initial antibodies randomly (a randomly generated non-repeating integer number between 1 and D+F-1 is assigned to each character of each antibody string). In general, the number N of initial antibodies (solutions) generated is determined according to the problem size.

Calculation of antibody affinity (1) Antibody fitness

For each antibody w, based on the scenario-based deterministic equivalence model in section 6.3.2 and the proposed Method in section 5.3.2.2 (Evaluation of a solution),

we can calculate the fitness 𝐴 𝑤 of w by formula (6.14) ,and then evaluate the quality of this antibody. Note that when we use the formula (6.1) (in section 6.3.2)to get the objective function 𝑣𝑎𝑙𝑢𝑒 𝐹 𝑤 𝑜𝑓 𝑖𝑡𝑠 𝑠𝑜𝑙𝑢𝑡𝑖𝑜𝑛 𝑤, we get the values of variables 𝑥 𝑖𝑗 𝑣 and y 𝑖 v which are represented by w, based on the antibody expression in section 6.4.2.1..

The sum of fitness of all antibodies is given by SA=∑ 𝐴 𝑤 𝑤∈𝑁 .

In each iteration of the immune genetic algorithm, the top m (m is taken as 10% to 20% of N) antibody individuals (in terms of fitness) are stored in a memory library.

Using this elitist strategy, after the antibody updating in each generation (iteration), the best antibodies and some better antibodies are put into memory. This immune memory mechanism (memory function) record each generation antibody group's optimal antibody group (Cheng and Zhong, 2014).

(

2)Antibody-antibody affinity

The antibody-antibody affinity reflects degree of the similarity degree between the antibodies. Here, the antibody-antibody affinity is defined referring to the R-bit Chapter 6. Route Planning of Freight Buses with Stochastic Demands for the scenario-based optimization problem which are also grouped in instances of small size (N∈{7,13}, M∈{3,5}), instances of medium size (N∈{20, 30, 40}, M∈{3,5})

and instances of large size (N∈{60, 80}, M∈{3,5}) instances (see Table 6.2). For all instances, the following data are same with the instances in chapter 5 : the coordinates of all nodes, the number of vehicles (freight buses), and the capacity of each vehicle (freight buses),the number of periods M, the unit distance operating cost γ, the penalty coefficient 𝛼 and 𝛽.

And in our instances, refer to [START_REF] Golden | Framework for probabilistic vehicle routing[END_REF], the delivery demand and the pickup demand of each depot in each period are assumed subject to Poisson distributions, with the average delivery demand and the average pickup demand of each depot i in each period k is randomly generated from [1,40]. The demands 𝑑 𝑖 (k)(l) and 𝑝 𝑖 (k)(l) in each scenario l are then randomly generated according the Poisson distributions. (The determination of the number of scenarios for different size of instances will be descripted in section 6.5.3.)

Parameter setting

We used CPLEX to solve the MILP model, and used Matlab to implement our Immune Genetic algorithm.

The parameters values were determined to achieve a good trade-off between solution quality and CPU time, as follows. For small instances: the population size of Antibodies = 30, the size of memory library = 5, the probability of crossover=0.9, the probability of mutation=0.4, and the maximum number of iterations=40. For medium instances: the population size of Antibodies=50, the size of memory library = 10,the probability of crossover=0.85, the probability of mutation=0.35, and the maximum number of iterations=50. For large instances: the population size of Antibody=80, the size of memory library = 15;the probability of crossover=0.8, the probability of mutation=0.3, and the maximum number of iterations=60.

Moreover, we preset its CPU running time to 7200,10800, 18000, 25200, 32400,

2) Estimate the standard deviation 𝜎(𝑛) of the costs obtained in 1) by formula (6.18).

3) Determine the number of scenarios N required for a given confidence interval H and level of confidence 𝛼 according to (6.19). If N ≥ n, stop. Otherwise, set n = N, and go to Step 1) (Nguyen and Chen,2018).

Based on the Monte Carlo sampling method, we set the number of scenarios to 40, 80, 200 for instances of small size, medium size, large size, respectively.

Experimental results

The performance indexes used in the performance evaluation of our Immune Genetic algorithm and their definitions are given in

𝐶𝑃𝑈 𝐼𝐺𝐴

The CPU time of the Immune Genetic algorithm (in seconds)

The following three tables give the computational results of small instances, medium instances, and large instances, respectively.