Sohrab Sepehri

Mohsen, Amer, Meisam, Elnaz Rezvan

Keywords: collaborative transportation planning, combinatorial auction, vehicle routing, multi-objective vehicle routing problem v plantification collaborative de transport, enchère combinatoire, problème de tournèe de véhicule

It is not our business to fathom the mystery of rose Perhaps our business is to float within the magic of the rose Camp behind wisdom And be born again when the sun rises in the mornings Let's allow our excitement to fly Let's lift down the burden of knowledge from the shoulders of the swallow Let's take back our name from the cloud From the plane tree, mosquito, summer Let's mount to the height of kindness of the wet feet of rain Let's open the door to mankind, light, plants and inspects Our business is perhaps To run between the lotus flower and the Centrury after the sound of truth

On the one hand, customers want to have products with low prices and on the hand, the increasing fuel costs and other costs have negative effects on the profit margin of logistics providers and the final prices of products [START_REF] Brewer | Handbook of logistics and supply-chain management[END_REF]. Forming collaborative networks and sharing resources and tasks are primary strategies for the companies to gain competitive advantages and capture more business opportunities. For this reason, carrier collaboration has attracted a growing interest of these logistics companies and has become an effective strategy for small to medium-sized carriers to reduce empty vehicles and increase vehicle fill rates [START_REF] Chen | Mathematical model and solution approach for collaborative logistics in less than truckload (LTL) transportation[END_REF]. Some implemented projects in USA disclose that Collaborative Transportation Management (CTM) (including carrier collaboration) can reduce the distance traveled by empty vehicles by 15%, the waiting time of vehicles by 15%, the turnover of drivers by 15% and can improve the fill rate of vehicles by 33% [START_REF] Chen | Combinatorial clock-proxy exchange for carrier collaboration in less than truck load transportation[END_REF].

Key issues in carrier collaboration

Forming an alliance among multi-carriers at the same level of logistics operations is called carrier collaboration. In the carrier collaboration, multi-carriers in an alliance exchange their transportation requests to discover better assignment of requests among them and improve the profit of each carrier.

Such re-assignment of requests plays an important role in improving routing planning, decreasing empty back-hauls of vehicles and consequently reducing transportation costs. The optimal re-allocation of requests among carriers is one major problem in carrier collaboration.

The objective of this problem is to maximize the total profit of all carriers in the alliance. Another problem in carrier collaboration is fair allocation of the profits obtained through the collaboration 1 CHAPTER 1. GENERAL INTRODUCTION among all carriers. This allocation of profits is usually made after collaborative transportation planning among carriers, which is called post-collaboration profit allocation. A fair allocation of such profits is necessary to guarantee the sustainability of the alliance [START_REF] Chen | Combinatorial clock-proxy exchange for carrier collaboration in less than truck load transportation[END_REF].

These two problems or issues will be introduced in the following. In this thesis, we focus on the first problem which is also referred to as collaborative transportation planning (CTP) problem [START_REF] Kopfer | Combining vehicle routing with forwarding: extension of the vehicle routing problem by different types of sub-contraction[END_REF], [START_REF] Wang | Collaborative transportation planning of less-than-truckload freight[END_REF].

The requests re-assignment problem

Carrier collaboration is usually realized by exchanging requests among multi-carriers. Through collaboration, small to medium-sized LTL carriers can increase asset utilization (reduce unused vehicle capacity) and strengthen their market positions. The challenge for such a collaborative effort is in finding a good balance between the requests assigned to each LTL carrier and its available transportation capacity to serve the requests. To ensure that such collaboration is sustainable, all participating carriers must benefit from it [START_REF] Hernández | A less-than-truckload carrier collaboration planning problem under dynamic capacities[END_REF]. There are two different approaches in carrier collaboration: Decentralized planning approach and centralized planning approach.

In centralized planning approach, the collaboration among carriers is realized by exchanging some requests (called exchangeable requests) among carriers. In centralized planning approach, a central coordinator allocates all transportation exchangeable requests to minimize the postcollaboration transportation cost of each collaborative carrier. In addition to the selection of requests for each carrier, optimal routes to serve the requests must be determined. To put it more precisely, in a centralized planning approach, a central coordinator is responsible for optimally re-assigning all exchangeable requests among all carriers to maximize their total profit. In a transportation network, each vehicle tour of a carrier is defined by a circuit that starts with and ends at the depot node of the carrier. The combinatorial nature of requests re-assignment problem is driven the difficulty problem. In addition to the selection of requests for each carrier, optimal routes to serve the requests must be determined.

In decentralized planning approach, some protocols like auctions are utilized to the request allocation. Each carrier may organize the protocols by participating in various protocols to maximize its post-collaboration profit. In this approach, a central coordinator is similar to an auctioneer who organizes the protocols to maximize the re-assignment profit among coalition carriers. Auction-based approaches are the most important methods for CTP. An auction is a process of buying and selling goods or services by offering them up for bid, taking bids, and then selling the item to the winning bidder. As important category of auctions, combinatorial auctions allow bidders to bid on combinations of objects, tend to lead to more efficient allocations. The bid generation problem (BGP) is a key decision problem for auction-based decentralized planning approaches in CTP, which is considered from the perspective of each carrier. The BGP can also be considered as the request selection problem. The combinatorial nature of requests re-assignment problem is driven the difficulty problem.

Comparing the two approaches, the decentralized approach can preserve the decision-making autonomy and the business data of each carrier confidentiality, whereas the total profit of all carriers generated by the centralized approach is usually higher than that generated by the decentralized approach, because of the global optimization nature of the centralized approach. The main concern of using a centralized approach for carrier collaboration is to keep the business data exchanged confidentiality among carriers. In recent years, with the appearance and development of Fourth-Party Logistics (4PL) providers who act as an integrator coordinating the transportation planning of multi-carriers without direct exchange of data among them, this concern is much eased. Moreover, it may be worthy for a carrier to reveal some information to the 4PLs in exchange of gaining a higher profit. Such a centralized planning approach is also used in collaborative transportation service trading in B2B e-commerce logistics [START_REF] Zhang | Optimal collaborative transportation service trading in b2b e-commerce logistics[END_REF].

In addition to the selection of requests for each carrier, optimal routes to serve the requests must be determined; since it is a type of the well-known NP-hard vehicle routing problems [START_REF] Wang | Collaborative transportation planning of less-than-truckload freight[END_REF].

The profit allocation problem

After the requests re-assignment, the profits are allocated to all carriers in a fair way.

Thorough this allocation, the post collaboration profit of each carrier is no less than the profit generated before collaboration and all carriers stay in the alliance. The profit allocation problem is a well known issue in the game theory. The big problem in this topic is, allocating the accepted profits for the all the carriers in alliance.

Inasmuch as there is not a unique definition for the fairness, the profit allocation problem is not unique allocation procedure. Thus, the design of an allocation approach is a difficult mechanism.

The problems studied in this thesis and contributions

In collaborative logistics, multi-carriers form an alliance to improve their transportation operations and profitability by exchanging their transportation requests. In this thesis, we focus on carrier collaboration in less-than-truckload (LTL) transportation. More precisely, we study some sub-problems appeared in collaborative transportation planning realized by a centralized approach and an auction-based decentralized approach.

Firstly, we focus on centralized collaborative transportation planning (CTP) among carriers in a less-than-truckload transportation environment, where each request is a pickup and delivery request with time window for both pickup and delivery operations. Each carrier may have exchangeable requests and reserved requests, which must be self-served by the carrier and the collaboration among carriers is realized by exchanging unreserved requests among them. The problem becomes a multi-carriers pickup and delivery problem with time windows, two different types of requests, exchangeable and reserved requests, which is a new variant of NP-hard vehicle routing problems [START_REF] Verdonck | Collaborative logistics from the perspective of road transportation companies[END_REF]. In spite of orienting problem which there is not compulsory to serve all re-quests [START_REF] Boussier | An exact algorithm for team orienteering problems[END_REF], in our problem all exchangeable requests have to be served. After presenting a mixed integer linear programming model to the problem, we propose an Adaptive Large Neighborhood Search (ALNS) algorithm, hybrid algorithm of Genetic and simulated Annealing algorithms (GASA) and Improved Tabu Search (ITS) to solve it. In [65], an ALNS algorithm is applied to solve a pickup and delivery problem with time windows, profits, reserved requests, and involving a single carrier with a single vehicle depot. In that problem which there is a single carrier, it is not compulsory to serve all exchangeable requests. The collaborative transportation considered in this thesis is a new problem involving multi-carriers with multi-depots. Furthermore, each reserved request must be served by its own carrier and all exchangeable and reserved requests must be served, the existing ALNS algorithms cannot be directly applied to our problem and some adaptations are necessary in order to solve our problem. The ALNS proposed in this thesis uses a variety of destroy/ repair operators. Its search procedure consists of multiple phases, where different phases use different policies for the choice of requests to destroy (delete) or repair (re-insert). The basic idea is to alter the behavior of destroy/repair operators over successive phase of the ALNS so it can explore different regions. In addition, local search based post-optimization is applied at the end of each phase in order to further improve the quality of the final solution obtained by the ALNS. The GASA takes advantages of genetic algorithm and simulated annealing at the same time (on the one hand, population-based criterion adds diversification and on the other hand, local search characteristic by applying SA prevents to be trapped in the local optimum). The Improved TS (ITS) adopts a mutation operator and keeps multiple solutions during the search process in order to get a better solution more quickly (Chapter 3).

Secondly, we study the multi-periods bid generation problem (BGP) for a carrier appeared in a multi-periods combinatorial auction for carrier collaboration. In real world applications, carriers usually plan their operations in a rolling horizon way. It means that each carrier determines which transportation requests to bid and serve in each period. Additionally, for exchangeable requests there is not fixed day to serve. Each request is allowed to be served within a period window consisting of multiple consecutive days. For example, goods ordered on-line by a customer on Monday in e-commerce is asked to deliver to the home of the customer within three days from Tuesday to Thursday. This gives rise to a multi-periods combinatorial auction (CA) problem. As a result, the bid generation problem of each carrier in such auction also involves multi-periods, where a bid is a combination of transportation requests over multi-periods [62]. Hence, in the problem, there are two different types of requests, reserved requests of the carrier and selective requests that are offered by other carriers and open for bid by the carrier. In selective requests, each pickup and delivery request is associated with two time windows. One is the period window which specifies the earliest period and the latest period the request must be served, whereas the other is a time window defining the earliest and latest service time of the request in each period.

For each reserved request, there is predetermined period. It means that, each reserved request must be served in the fixed period. Moreover, both of the pickup and delivery request in reserved 1.2

. THE PROBLEMS STUDIED IN THIS THESIS AND CONTRIBUTIONS

request have their own time window to serve. A carrier must make two important decisions in the BGP: Which requests are chosen to bid and serve in their period window and how the routes are constructed to maximize its total profit. This leads to a new periodic pickup and delivery problem with time windows, profits and reserved requests with widespread use in the real application.

A hybrid Genetic and Simulated Annealing algorithm and a Biogeography-Based Optimization algorithm are developed to solve the problem after presenting a MILP model. Hence, a hybrid approach that combines genetic algorithm and simulated annealing (GASA) is proposed to solve the problem. The GASA adopts a problem-specific chromosome structure, crossover and mutation operators well adapted to the chromosome structure. For the purpose of comparison, we also utilize a Biogeography-Based Optimization algorithm (BBO) that is a population-based algorithm and its specifications are close to the GA and its operation is over the population of solutions to search the best solution for the problem. By comparing GA and BBO, each chromosome in GA, which is considered as an individual with fitness value, is habitat with suitability index that is called HSI (Habitat Suitability Index) (Chapter 4). In reality, besides minimizing costs, shippers also pay attention to the reduction of the delivery lead time. Shorter delivery lead time makes orders can be delivered to customers faster. Therefore, to make bids competitive, carriers also need to consider delivery lead time as a quality specification when they construct their bids.

For the auctioneer, it has two ways to evaluate each bid from carriers. One is evaluating a bid according to a score function that is defined as cost and delivery lead time as in a multi-attributes score auction. The other is evaluating a bid according to its multi-attributes (in our case, one attribute is price, the other attribute is the delivery lead time). Accordingly, each carrier has also two ways to submit its bid, one is submitting a score (cost and delivery lead time) and the other is submitting both attributes of a bid (cost and delivery lead time). Thus, to solve the problem, the multi-periods BGP becomes a bi-objective problem. There are two methods to deal with a biobjective problem: The first approach is a weighted objective method, that is, we assign a weight to each objective and then transform two objectives into a single weighted objective. The other method is a bi-objective method, which is treated with all objective functions separately without transforming them into a single objective function. Consequently, two methods of treatment with the two assumed objectives lead to two problems: Single objective multi-periods BGP with delivery lead time and bi-objective multi-periods BGP with delivery lead time. After presenting MILP models to the both problems, to solve the single objective multi-periods BGP with pickup and delivery problem with time windows, profit, and delivery lead time, we apply GASA and ITS and to solve a bi-objective mathematical model formulation, two algorithms NSGAII and NRG are proposed to solve the model. The proposed algorithm to solve the bi-objective problem are compared based on a number of well-known metrics, as in Chapter 5 we refer to them.

Conclusion

Collaborative logistics has attracted many attentions both in academic community and industrial practitioners in recent years because of its great significance in saving transportation costs. In this thesis, a carrier collaboration problem in pickup and delivery service with time windows and LTL transportation is studied. We develop a series of mathematical models and multiple solutions approaches for the problem. Chapter 1 mainly introduces our research background and generally describes the problems studied in this thesis. Chapter 2 provides an overview of current-art of collaborative transportation planning. A general review is given firstly to the field of collaborative logistics. Then the literature review focuses on significant contributions and important review papers on the centralized and decentralized planning approaches, especially the bid generation problem for carrier collaboration. Chapter 3 is devoted to solve the centralized collaborative transportation with pickup and delivery services, time windows and reserved requests. Chapter 4 focuses on multi-periods bid generation problem. Chapter 5 solves the Single objective and Bi-objective multi-periods BGP with delivery lead time concept. At last, Chapter 6 concludes this thesis and present the perspectives of future works opened in the field of collaborative transportation planning.

C H A P T E R 2 LITERATURE REVIEW T he specialize of the fright logistics is in the cargo forwarding among places. In the last decades, which the use of e-commerce has increased dramatically, freight forwarding plays a vital role in daily economic activities. Hence, the freight logistics rapidly developments leads an intense competition among freight carriers. Furthermore, diminishing the profit margins of carriers, pivots on the increasing the fuel costs, enhances customer satisfaction and labor prices and reduces the life cycle of products [START_REF] Cruijssen | Horizontal cooperation in logistics: Opportunities and impediments[END_REF]. So, for carriers, it is a real challenge to how to survive in such fierce competition environments. Collaborative Logistics (CL) or Collaborative Transportation Management (CTM) are developed to overcome these challenges. The horizontal cooperation that is active at the same level of SCM, can be defined among carriers/shippers [START_REF] Verdonck | Collaborative logistics from the perspective of road transportation companies[END_REF]. Two types of horizontal collaborative logistics are specified in the literature: Shipper collaboration and carrier collaboration. The shipper collaboration contemplates on a single carrier and multi-shippers. In this type of collaboration, shippers consolidate all transportation requests to be afforded by a carrier. In the collaboration, asset repositioning costs are diminished by the shippers. Nevertheless, in the last years, most researchers have focused on the carrier collaboration. Actually, in carrier collaborations, there are opportunities for carriers to exploit the alliance among their transportation requests as on the one hand, reduce lead time and cost and on the other hand, improve the overall service levels [33]. The differences between carrier collaboration and shipper collaboration are explained in details in [START_REF] Okan Örsan Özener | Lane-exchange mechanisms for truckload carrier collaboration[END_REF], [START_REF] Hernández | A carrier collaboration problem for less-than-truckload carriers: characteristics and carrier collaboration model[END_REF]. Consequently, horizontal cooperation drives CL or CTM by either sharing transport capacities or transportation orders by making use of information technology, which has been developed in recent years. Thus, all involved actors can enhance their profitability by eliminating empty back-hauls; so the vehicles usage rates augments [START_REF] Dai | A multi-agent and auction-based framework and approach for carrier collaboration[END_REF].

In the realistic logistics services, truckload (TL) transportation and less-than truckload (LTL) CHAPTER 2. LITERATURE REVIEW transportation are the two types of logistics services provided to the customers. The movement of large amounts of homogeneous cargoes between two places is called TL shipping, while LTL refers to the small freights shipping among multiple places. For LTL shipment, customers pay according to the amount of occupied space of truck capacity, whereas in TL transportation, customers pay to the entire truck. Accordingly, in the case of shipping small freights, customers make use of this privilege and share the space of a truck with other customers. For small to medium sized enterprises without ability to provide TL shipping, LTL shipment is an ideal option.

Transportation tools such as vans or vehicles are referred as truck in this thesis and henceforth the terms can be exchangeable. Exchanging (re-allocating) requests among carriers to minimize costs is a main issue in the carrier collaboration. To this reason, in the last years, industerial and academic centers take attention to the collaborative transportation planning (CTP) [START_REF] Wang | Collaborative transportation planning of less-than-truckload freight[END_REF], [START_REF] Wang | Increasing efficiency of freight carriers through collaborative transport planning: Chances and challenges[END_REF], [START_REF] Wang | Operational transportation planning of freight forwarding companies in horizontal coalitions[END_REF], [START_REF] Kopfer | Combining vehicle routing with forwarding: extension of the vehicle routing problem by different types of sub-contraction[END_REF]. Fairly allocate the post-collaboration profit among carriers through CTP, is the other issue to provide the sustainability. Although in this thesis we address the first issue in LTL mode, the readers can refer to the recent review in this issue [START_REF] Guajardo | A review on cost allocation methods in collaborative transportation[END_REF].

Centralized and decentralized planning approaches are the two techniques for CTP in LTL. In centralized planning approaches, there is a central coordinator who is responsible to re-allocate (exchange) the transportation orders optimally among carriers inasmuch as their cost is minimized. In contrast, in decentralized planning approaches, there is no central coordinator to organize all plans of the carriers and each carrier performs like an independent agent. Totally, the main differences between centralized and decentralized planning approaches return to clarify all information of the orders of a carrier to other carriers in coalition. In the centralized planning approaches, all order information of each carrier is shared with other carriers in alliance, whereas in decentralized planning approaches only limited information is shared among coalition carriers.

In realistic applications, although centralized approaches are often superior to decentralized methods regarding to minimize total cost, carriers are not only partners and competitors may be choose to conceal the information of customers'orders; so decentralized approaches are more practical [START_REF] Verdonck | Collaborative logistics from the perspective of road transportation companies[END_REF].

The rest of this chapter will be organized as follows: A brief literature review on vehicle routing problems with pickup and delivery and time windows that are related to the studied subject in the thesis will be given in Section 2.1. A general literature review on collaborative logistics will be considered in Section 2.2. Since the two sub-problems studied in this thesis are related to the class of decentralized planning approaches and just one sub-problem applies the centralized approach, in Section 2.3 brief review on centralized planning approaches is given and a general review on decentralized planning approaches will be given in Section 2.4.

VEHICLE ROUTING PROBLEM WITH PICKUP AND DELIVERY AND TIME WINDOWS

Vehicle Routing Problem with Pickup and Delivery and

Time Windows

The latest studies in vehicle routing problems (VRP) and various specifications are considered in the book [START_REF] Bruce L Golden | The vehicle routing problem: latest advances and new challenges[END_REF]. In that review chapter, the authors are presented variety of problems like heterogeneous vehicles and time window. They proposed mathematical models and heuristic approaches to solve the different types of vehicle routing problems. Vehicle routing problems often are known by some properties to take into account the specificities of real applications. Heuristics and meta-heuristic algorithms for Multi-Attributes Vehicle Routing Problems (MAVRP) are presented in [START_REF] Vidal | Heuristics for multi-attribute vehicle routing problems: A survey and synthesis[END_REF] as a review study. One part of the studied problem in this thesis is close to the multi-depots vehicle routing problem with pickup and delivery requests and time windows (multi-depots VRPPDTW). Our problem is different from classical multi-depots VRPPDTW as in the assumed problem in this thesis, two requests are considered and it will be included the aspects of CTP. Therefore, it is beneficial to study some works in the multi-depots VRPPDTW.

The mathematical model for multi-depots vehicle routing problems (multi-depots VRP) with time windows is suggested in [START_REF] Bae | Multi-depot vehicle routing problem with time windows considering delivery and installation vehicles[END_REF]. In the paper, the mathematical models are applied in the delivery and in the installation of electronic equipment. The authors present mixed integer linear mathematical model (MILP) to minimize total costs. They solve the model by a genetic algorithm.

The efficiency of the proposed solution is proved by reaching near-optimal solutions. A new type of multi-depots VRPPD with time windows is studied in [START_REF] Kachitvichyanukul | Two solution representations for solving multi-depot vehicle routing problem with multiple pickup and delivery requests via pso[END_REF]. In this type of VRP, the depot, where the vehicles return to it is flexible. An integer mathematical model to minimize the total travel cost is presented to the problem and a hybrid genetic algorithm with adaptive local search is proposed to solve. In the VRPPDTW problem studies by [START_REF] Ropke | An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows[END_REF], the starting depot and destination depot of each request do not need to be the same. Metaheuristic algorithm to solve the problem is ALNS and the authors show the efficiency of the algorithm. In truth, ALNS algorithm is presented by [START_REF] Pisinger | A general heuristic for vehicle routing problems[END_REF] and it is used in the different fields of VRP because of its efficiency in acting on the neighborhood.

Collaborative logistics

In [START_REF] Cruijssen | Horizontal cooperation in logistics: Opportunities and impediments[END_REF], a large-scale review on the opportunities and obstacles of horizontal collaboration in logistics is described. Generally, the advantages of horizontal collaboration on the quality of logistics services are strongly acceptable by logistics service providers (LSPs). Nevertheless, one of the expected obstacles in horizontal collaboration is a fair allocation of profit and it is considered as a hardest challenge. In [START_REF] Kopfer | Approaches for modelling and solving the integrated transportation and forwarding problem. Produktions-und Logistikmanagement[END_REF], existing approaches to model and solve collaborative transportation and different challenges of the issue are provided. The problem is an expanded problem of vehicle routing problems as freights can be supplied by 4th party logistics. The mentioned survey paper indicates why there are gaps between theory and practice. Another prominent survey in the field of collaborative logistics is studied by [START_REF] Amours | Issues in collaborative logistics[END_REF]. At first, the opportunities in the CTP are outlined and then the key issues in the coalitions like sharing resources, profits, information are discussed. Finally, the authors depicted the approaches of information protection and decisions technologies. Moreover, in the article, some business cases have been dedicated to support the problem. Another literature review in horizontal collaborative logistics is presented in [START_REF] Verdonck | Collaborative logistics from the perspective of road transportation companies[END_REF]. In this study, the horizontal logistics collaboration is categorized into two methods: Order sharing and capacity sharing. For two methods, solution approaches are discussed in details. By applying order sharing approaches and property repositioning abilities, the transportation costs are reduced and the efficiency of transportation planning is enhanced. According to the existing studies, there are different approaches to order sharing and re-allocation of requests to optimize the logistics system. In the paper, authors classify different techniques in the order sharing: Joint route planning, auction-based mechanisms, bilateral lane exchanges, load swapping, and shipment dispatching approaches. Another method in collaborative transportation planning is sharing customer orders, which is provided by carrier collaboration and horizontal collaboration through sharing vehicles capacity. By making use of this way, on the one hand, empty backhauls is reduced and on the other hand, the capital expenses can be shared among all coalition carriers. Two general approaches are provided by previous studies to establish the most efficient way to share vehicle capacities. One of the approaches is mathematical programming and another is based on the negotiation protocols.

Centralized planning approaches for collaborative transportation

For centralized planning approaches in collaborative logistics with TL transportation, the authors in [30] are proposed a Lane Covering Problem (LCP), which arises in the context of shipper collaboration. The object function of the model aims to find a minimum cost of directed cycles set (truck tours), not necessarily disjoint, covering a given subset of arcs (lanes) in a complete euclidean digraph. Effective algorithms and efficient implementations for solving the LCP are also developed in this paper. In later studies, the authors are considered some constrained variants of LCP, such as the cardinality constrained LCP [32], the length constrained LCP [30], the dispatch windows constrained LCP and driver restriction LCP [31]. The potential collaborative opportunities among carriers in TL transportation is investigated in [START_REF] Okan Orsan Ozener | Collaboration for truckload carriers[END_REF]. In the proposed optimization models, carriers' repositioning costs may be reduced by exchanging transportation requests.

Various exchange mechanisms are designed and evaluated, differing in terms of information sharing requirements and side payment options, which allow carriers to realize potential costs savings opportunities.

For centralized planning approaches in collaborative logistics with LTL transportation, a single-carrier collaboration problem (SCCP) is studied in [START_REF] Hernández | A carrier collaboration problem for less-than-truckload carriers: characteristics and carrier collaboration model[END_REF], in which a carrier seeks to collaborate with other carriers in order to acquire extra transport capacity to service excess demand. The

DECENTRALIZED PLANNING APPROACHES FOR COLLABORATIVE TRANSPORTATION

SCCP is considered from a static planning perspective to gain insights into the potential benefits of the collaboration concept for carriers, and its ability to mitigate the consumption of fuel. The collaborative strategies are evaluated by computing the relative benefits of the collaboration over the non-collaboration situation. Single and multiple-products SCCPs are both formulated as binary (0-1) multi-commodities minimum cost flow problems, and the models are solved by a branch-and-cut algorithm.

Decentralized planning approaches for collaborative transportation

Auction-based methods are applied for decentralized planning in collaborative logistics. A protocol which is called auction, allows the agents to specify their interests in the resources and utilize their interest to assign the resources and payments among the agents. The winners of the bids are known as a NP-hard problem and combinatorial auction problem (CAP) is employed to determine the winners of the bids. Hence, combinatorial auction is specifically probed in a decentralized planning issue. To implement combinatorial auction in the collaborative transportation, there is a central coordinator who is responsible to all auctions taken place during the collaboration planning process.

In [59], a multi-rounds combinatorial auction technique is suggested in truckload transportation, where shippers permit to bids on the requests. In fact, in each round, a bid generation problem (BGP) is solved by each carrier to find the most profitable pack of requests. In this case, the winner determination problem (WDP) is solved by the auctioneer to allocate the requests to the carriers [START_REF] Song | Combinatorial auctions for transportation service procurement: The carrier perspective[END_REF], [93], [63]. In CTP, the bid generation problem (BGP) is an important decision approach for auction-based decentralized planning issues and is considered from each carrier' viewpoint. To add to this fact, the BGP can also be used as a request selection strategy. Our study in chapter 4 and chapter 5 are related to the request selection problem, so the BGP will be reviewed in details in section 2.4.2.

Auction-based Mechanisms

The key strategies for CTP are the Auction-based approaches. The process of buying and selling products by proposing them for bid and selling the items to the winner bidder is called Auction.

According to the literature, auctions are classified to four groups: Single-object auctions, multipleobjects auctions, combinatorial auctions (CA), and exchanges [START_REF] Shoham | Multiagent systems: Algorithmic, game-theoretic, and logical foundations[END_REF], [58]. Combinatorial auctions are the most popular and important strategy that allow bidders to bid on the combination of products and allocate them efficiently.

However, maximization revenue and determining the winners in CTP by combinatorial auctions is NP-hard problem [START_REF] Sandholm | An algorithm for optimal winner determination in combinatorial auctions[END_REF].

Bid generation problems (BGP)

The BGP in carrier collaboration can be considered as deterministic BGPs and stochastic BGPs.

In this thesis we focus on deterministic information; so deterministic BGPs will be exploited.

In [START_REF] Wang | Combinatorial bid generation problem for transportation service procurement[END_REF], the concept of BGP in carrier collaboration transportation service is addressed. In the

Conclusion

I

n this chapter, we study centralized planning approach for multi-carriers collaboration in a less-than-truckload transportation environment, where each carrier has a finite number of vehicles and each request is a pickup and delivery request with time windows. In this problem, each carrier may have reserved requests, which must be self-served by the carrier.

In fact, two types of actors exist in our centralized planning approaches: Central coordinator and carriers. Multi-carriers come to an agreement for constituting a collaborative alliance with a central coordinator in charge of making collaborative transportation plans for them. The coordinator is a virtual actor who re-allocates the transportation requests of the alliance to all carriers. By exchanging some requests among them, such collaboration can help them to reduce transportation costs and increase profits. It can be realized via a Fourth-Party Logistics (4PL) provider who acts as an integrator coordinating the transportation planning among carriers.

In the carrier collaboration, several carriers form an alliance and exchange some transportation requests. Each carrier has a set of reserved requests (i.e. not proposed for exchange in CA/CE) and can serve additional requests (exchangeable requests) acquired from other carriers. Each request is a pickup and delivery request associated with an origin, a destination, a quantity, two time windows (pickup time window and delivery time window), and a price (revenue) for serving the request paid by its corresponding shipper (customer). In spite of orienting problem which there is not compulsory to serve all requests [START_REF] Boussier | An exact algorithm for team orienteering problems[END_REF], in our problem all exchangeable requests have to be served. so it can explore diverse regions. In addition, local search based post-optimization is applied at the end of each phase in order to further improve the quality of the final solution obtained by the ALNS. For the purpose of comparison, we also develop a Hybrid Genetic Algorithm combined with Simulated Annealing (GASA). The GASA adopts a problem-specific chromosome structure, crossover and mutation operators well adapted to the chromosome structure. We also develop an Improved Tabu search (ITS) approach. This approach improves classical Tabu search by keeping multiple solutions during the search process, collecting and using the information about them in order to improve the current solution more quickly [75]. Moreover, we use a mutation tactic which is another technique to improve the performance of this algorithm [START_REF] Jia | An improved tabu search approach to vehicle routing problem[END_REF]. The performance of the proposed algorithms are evaluated by comparing them with commercial solver CPLEX on 50 benchmark instances in [START_REF] Chen | Combinatorial clock-proxy exchange for carrier collaboration in less than truck load transportation[END_REF]. Numerical results show that ALNS, GASA, and ITS algorithms can obtain a better solution in a computation time much less than CPLEX commercial optimization solver. CPLEX could not even find a feasible solution after a limited running time for medium and large instances. Furthermore, the results show the cost obtained by ALNS and its running time are better than the cost and the running time achieved by GASA and ITS. This chapter is organized as follows. In Section 3.1, literature review on collaborative logistics and vehicle routing problems related to our work is given. The description of the problem and a mathematical model are provided in Section 3.2. Section 3.3 is devoted to the description of the applied ALNS, GASA, and ITS algorithms. In section 3.4, numerical results of comparing ALNS, GASA, and ITS algorithms with CPLEX solver on benchmark instances are reported and analyzed. Finally, Section 3.5 closes this chapter.

LITERATURE REVIEW

Literature review

Various types of cooperative relationships in the field of transportation and logistics have been discussed in both professional and academic literature. Both vertical cooperation and horizontal cooperation in supply chains are the focus of various research efforts over the last two decades. In recent years, horizontal collaboration which takes place among multiple firms at the same level of supply chain emerged as a promising framework to implement collaborative logistics [START_REF] Krajewska | Transportation planning in freight forwarding companies. Tabu search algorithm for the integrated operational transportation planning problem[END_REF], [START_REF] Wang | Operational transportation planning of freight forwarding companies in horizontal coalitions[END_REF], [START_REF] Dai | A multi-agent and auction-based framework and approach for carrier collaboration[END_REF]. Due to the increase in fuel costs, transportation companies are forced to use their vehicles more efficiently, which is given rise to CL or Collaborative Transportation Management (CTM).

Driven by cost reduction requirements due to fierce competition in the transportation market and increased environmental concerns, improving operational efficiency through resource sharing and collaborative transportation planning is becoming a new business model for transportation industry [START_REF] Amours | Issues in collaborative logistics[END_REF]. This is why collaborative logistics has received much attention in recent years.

As mentioned earlier, carrier collaboration in LTL can be realized by using two different types of approach, centralized and decentralized. For a centralized planning approach used in LTL collaborative logistics, a coalition multi-commodities game is studied in [68]. Players have a capacity and are the nodes of a given transportation network. A capacity defines the maximum flow permitted through the node. The optimal flow is obtained by solving a centralized planning problem and the total revenue is allocated to players in a fair way. A time-dependent centralized multi-carriers collaboration problem is studied in [START_REF] Hernández | A less-than-truckload carrier collaboration planning problem under dynamic capacities[END_REF], where a central entity seeks for minimizing the total costs of all carriers. They formulate the problem as a binary multi-commodities minimum cost flow model, and solve it by a branch and cut algorithm. The obtained results confirm the attractiveness of the centralized cooperation approach in the increase of vehicle capacity utilization and the decrease of empty-haul trips for carriers. In decentralized planning approaches, there is a central coordinator takes charge of all auction activities taking place in an auctionbased collaborative planning process. Where an auction is a protocol and allows agents to indicate their interests in one or more resources, uses these indications of interest to determine both an allocation of resources and an allocation of payments among the agents [START_REF] Dai | A multi-agent and auction-based framework and approach for carrier collaboration[END_REF]. For combinatorial auction applied to a collaboration among independent freight forwarding entities, a decentralized combinatorial auction model is proposed in [START_REF] Krajewska | Transportation planning in freight forwarding companies. Tabu search algorithm for the integrated operational transportation planning problem[END_REF]. The problem studied in this thesis is related to multi-depots vehicle routing problems with pickup and delivery requests and time windows (multi-depots VRPPDTW). There are not various papers in this field and most VRP articles are concentrated on VRP with each specification. In [START_REF] Sitek | Capacitated vehicle routing problem with pick-up and alternative delivery (cvrppad): model and implementation using hybrid approach[END_REF] Capacitated vehicle routing problem with pickup and delivery is presented. The authors focus on alternative delivery node and after presenting mathematical model, apply hybrid heuristic approach to solve the model. Our problem is different from them and from classical multi-depots VRPPDTW because of a new feature, i.e., the reserved requests of each carrier must be assigned to its own depot since these requests must be served by the carrier itself [START_REF] Kachitvichyanukul | Two solution representations for solving multi-depot vehicle routing problem with multiple pickup and delivery requests via pso[END_REF]. In this type of VRP, the depot, where the vehicles return to it is flexible. An integer mathematical model to minimize the total travel cost is presented to the problem under constraints of VRP. A hybrid genetic algorithm with adaptive local search is proposed to solve. In their problem, all customers have their own time windows, all routes start and finish at the same depot. Some articles in VRPPDTW are considered in the following. A mathematical model is studied in [START_REF] Ropke | An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows[END_REF] for the problem, whereas the starting depot and destination depot of each request do not need to be the same. Metaheuristic algorithm for the model is ALNS and the authors prove that the efficiency of algorithm is very high. ALNS algorithm is presented by [START_REF] Ropke | An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows[END_REF] and it is used in different fields of the VRP because of its efficiency in acting on the neighborhood. Traveling time from node i to node j, it is assumed equal to traveling time T Time duration of each route BM i, j = l j -e i Used in time window constraints

CV i = Q + d i
Used in vehicle capacity constraints re-allocated all exchangeable requests among carriers to minimize their total transportation cost to serve all reserved requests and exchangeable requests. We adopt a centralized approach to solve the problem. To do so, we first formulate this problem as a MILP. Table 3.1 and Table 3.2 list the indices, parameters, sets, parameters and decision variables used in the model sequentially.

The problem can be formulated as the following mixed integer-programming model: min m∈M i∈V j∈V k∈K m c i j x i jkm subject to:

j∈V , j =i x jikm - j∈V ; j =i x i jkm = 0 ∀i ∈ W, ∀k ∈ K m , ∀m ∈ M (3.1) m∈M j∈V ; j =i k∈K m x i jkm = 1 ∀i ∈ W (3.2) j∈P; j =i x i jkm ≤ 1 ∀k ∈ K m , ∀i = m ∈ M (3.3) j∈P; j =i x i jkm = 0 ∀k ∈ K m , ∀i, m ∈ M, i ∉ {m} (3.4) j∈D; j =i x i jkm ≤ 1 ∀k ∈ K m , ∀i = m ∈ M (3.
x i jkm = 0 ∀k ∈ K m , ∀i, m ∈ M, i ∉ {m} (3.6) k∈K m y ikm = 1 ∀i ∈ R m , ∀i, m ∈ M (3.7) k∈K m y ikm = 0 ∀i ∈ R, i ∉ R m r , ∀i, m ∈ M (3.8) m∈K m m∈M y ikm = 1 ∀i ∈ R s (3.9)
j∈V , j =i,m

x i jkm = y ikm ∀i ∈ P, k ∈ K m , ∀m ∈ M (3.10) j∈V , j =i,m x j(i+n)km = y ikm ∀i ∈ P, k ∈ K m , ∀m ∈ M (3.11) U ikm + t i(n+i) + s i ≤ U (n+i)km ∀i ∈ P, k ∈ K m , ∀m ∈ M (3.12) U jkm ≥ U ikm + t i j + s i -BM i j (1 -x i jkm ) ∀i ∈ V , k ∈ K m , ∀m ∈ M, ∀ j ∈ W (3.13) e i ≤ U ikm ≤ l i ∀m ∈ M, ∀i ∈ W (3.14) U ikm + t i j + s i -BM i j (1 -x i jkm ) ≤ T ∀i ∈ W, k ∈ K m , ∀m ∈ M, ∀ j ∈ M (3.15) L ikm + d i -Q(1 -x i jkm ) ≤ L jkm ∀i ∈ V , k ∈ K m , ∀m ∈ M, ∀ j ∈ V (3.16) max{0, d i } ≤ L ikm ≤ min{Q, CV i } ∀i ∈ V , k ∈ K m , ∀m ∈ M (3.17) j∈W k=1 x jikm ≤ K m ∀i ∈ M, ∀m ∈ M (3.18) x i jkm ∈ {0, 1} ∀i, j ∈ V , ∀k ∈ K m , ∀m ∈ M (3.19)
y ikm ∈ {0, 1} ∀i ∈ R, ∀k ∈ K m , ∀m ∈ M (3.20) U ikm ≥ 0 ∀i ∈ V , ∀k ∈ K m , ∀m ∈ M (3.21) L ikm ≥ 0 ∀i ∈ V , ∀k ∈ K m , ∀m ∈ M (3.22)
The goal is to minimize the total transportation cost of all carriers. The constraint (3.

Solution procedure

Construction of initial solution

To speed up the convergence, construct a good initial solution is important with some modifications to provide service for all exchangeable requests. The most important hypothesis is allocating all reserved requests and exchangeable requests to all carriers. Therefore, in the implementation of heuristic initial solution this specification should be considered. In the proposed heuristic, firstly, each carrier self-served to reserved requests. After that, each exchangeable request is inserted into an existing route of a carrier according to a chosen policy. Before assigning requests to the routes of any carrier, all reserved requests and all exchangeable requests are placed respectively in two lists, ordered according to their profits. Both reserved requests and exchangeable requests are assigned one by one in terms of order in their list. After assigning all reserved requests to the created routes of their own carriers, exchangeable requests are assigned to the existing routes of all carriers via the following two policies:

Policy one: After assigning all reserved requests of each carrier to its own routes, each exchangeable request is assigned to a carrier that both pickup and delivery nodes of the exchangeable request have a minimum distance to the depot of a carrier.

Policy two: After assigning all reserved requests of each carrier, each exchangeable request is allocated to a route of the best carrier with the lowest insertion cost.

Although, the first policy is a basic rule to assign exchangeable requests, there is a probability to set in local optimum. In comparison with first policy, the second policy is better to allocate exchangeable requests. An exchangeable request is assigned to a depot of a carrier according to the priority of a carrier. Total distance of pickup and delivery nodes of each exchangeable request to each carrier is calculated. The carrier with the minimum distance has first priority to allocation; second priority is related to a carrier with the distance larger than the minimum distance to the exchangeable request and so on. Each exchangeable request is allocated to the carriers according to their priorities. In fact, by allocating each exchangeable request to all carriers, there is a chance to select the best carrier. After assigning, we calculate the value of objective function, total cost, due to the constraints. The carrier with minimum cost is the exchangeable request carrier.

Globally, the first policy is not better than the second policy, but it gives a chance to first possible position to reach a better solution in a reduced time. While policy 2 is more acceptable to reach a better solution, this policy needs more time.

ALNS algorithm

The quality of a local search heuristic depends on how the neighborhood of each solution is defined. The larger neighborhood and the higher quality of the final solution may be found by the heuristic. When a problem has tight constraints, search a small neighborhood may fail to explore the solution space thoroughly, because in this case the local search may be trapped in a local optimum of poor quality [START_REF] Deniz Aksen | An adaptive large neighborhood search algorithm for a selective and periodic inventory routing problem[END_REF]. Large Neighborhood Search (LNS), which proposed in [START_REF] Shaw | Using constraint programming and local search methods to solve vehicle routing problems[END_REF] for vehicle routing problem with time windows, one ruin operator and one repair operator are alternatively selected in each iteration. Each ruin operator removes some customers from the routes of current solution. In contrast, the role of repair operators is transforming a partial solution into a complete solution by re-inserting the removed customers into the routes of the partial solution. ALNS has been extended LNS by adding an adaptation layer. This layer adaptively chooses in each iteration a ruin operator and an insertion operator among a set of operators to intensify the search. Moreover, simulated annealing is used in the high layer of ALNS and allows a worse solution is accepted under some conditions to diversify the search. Thus, ALNS can be considered an improved version of LNS.

At each iteration, a pair of ruin and repair operators are selected according to the historical performances of all operators, where a score, which is updated, or keeps unchanged in each iteration, measures the performance of each operator. In other words, the probability to select an operator in each iteration depends on its score. Although the choice of this pair of operators is randomized, the historical performances help to choose the most effective pair of ruin and repair operators, because a level (layer) of adaptation is added over the local search level of ALNS in this procedure. The ALNS algorithm proposed in this thesis can be considered an adapted version of ALNS in [65], [START_REF] Ropke | An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows[END_REF]. The procedure of the ALNS algorithm is outlined with pseudo-code in Algorithm 1.

In the current section, we described the ALNS procedure and how it is adopted to our problem. Firstly, multiple ruin and repair operators are designed by considering reserved requests Algorithm 1. Pseudo-code of the ALNS algorithm.

1

In each nruns runs (nruns is the maximum number of runs allowed) 2

Construct an initial solution 3

Set the best solution S best to the initial solution 4

Initialize starting temperature T 0 5

Initialize the weights and scores of all ruin/repair operators 6

In each nseg segments; nseg is the maximum number of segments allowed 7

Choose the polices for the selection of requests 8

In each niters iteration(niters is the maximum number of iterations allowed) ANLS to diversify the search in order to obtain a high quality solution. Finally, to enhance the intensification, local search with four moves is applied at the end of each phase to further improvement of current solution. All parts of the algorithm are described in the following sections.

Adaptive choice of ruin/repair operators

The ALNS chooses one ruin and one repair operator in each iteration according to the past performances of all operators. It gives a chance to all possible ruin/repair operators to be selected by the algorithm, even for operators of low performance, by using the roulette wheel method. Suppose there are in total c operators numbered from 1 to c. Each operator i = (1, 2, .., c) is associated with a weight W i . The weight reflects the performance of this operator in the past.

Thus, the probability of choosing each operator i is

W i c j=1 W j .
At the beginning of algorithm, the weight W i of each operator i is set to one. It is adjusted at the end of each phase according to its performance score. For all scores, the weights of all operators are updated at the end of each phase in the following way. At the beginning of each phase, the scores of all operators are set to zero. By this setting, all operators including inefficient operators in the previous phase have a chance to be selected. Four scores denoted by s 1 , s 2 , s 3 and s 4 , which correspond to four different situations are defined and their update in different situations are described in Table 3.3. In the first one, a new best solution is found; this is the most favorable case. About second and third situations, both them are also favorable because the obtained solution improves the current solution. Comparing second and third situation, the second one is more attractive since it explores a new region of the solution space. In fact, in the second situation, the algorithm finds a solution with new features. To know our algorithm has found a new solution, storing some attributes of the solutions previously found is compulsory. These attributes can be the number of requests served by the available vehicles, the number of vehicles used and the total profit. Hence, there is a list to store all profits in an increasing order and dichotomy search is used to check a solution with a given cost. Finally, fourth type of score brings some diversification to the search as it prevents from using the same operators frequently. This score depends on the acceptance criteria of SA used in the algorithm. Let W i,se be the weight of operator i in se phase, tc i,se be the number of times that operator is selected by the algorithm, f c i,se is the final score of operator i at the end of phase se. rt ∈ (0, 1) is a reaction factor and indicates which degree of weight in each operator reacts to its performance. If rt = 1, the current weight of each operator is disregarded and its new weight only depends on its achieved score in the last phase. If rt = 0, the current weight of each operator is preserved while its achieved score is overlooked. Finding a new solution which improves the current solution. s 3

The solution found is not new but improves the current solution. s 4

The solution found is accepted by SA although it is worse than the current solution.

By mentioned four scores at the end of each phase, the weights of all operators are updated in each phase according to the following equation (3.23).

w i,se+1 = 1 -rt × w i,se + rt × - f c i,se tc i,se (3.23)

The rules of selecting requests by ruin/repair operators in each phase

As mentioned above, in ALNS, different phases use different policies for the selection of requests to remove (ruin) and the requests to re-insert (repair). In our problem, because all exchangeable requests must be served, the rules of applying ruin/repair operators for requests are the two following suitable policies.

Request selection policies for ruin operators 1. All requests are removable.

2. Only exchangeable requests are removable.

Request selection policies for repair operators

1. There is no difference between exchangeable requests and reserved requests when choosing a request to re-insert by a repair operator.

2. The priority of reserved requests is higher than that of exchangeable requests when choosing a request to reinsert by a repair operator.

The first policy is denoted by policy 1 and the second policy is called policy 2. The two policies are compatible with the nature of our problem. In the following, we describe two policies and their implementation.

If policy 1 is chosen, there is no difference between two types of requests when they are removed or re-inserted. In other words, any request can be served as long as all the constraints of the problem are satisfied and the corresponding ruin/repair operator is feasible. With time windows and vehicle capacity constraints in our problem, a ruin or repair operator may lead to an infeasible solution. Such situation may happen when some reserved requests are not served.

Generally, the role of the first policy is to expand the search space by possibly selecting all requests.

In this case, some reserved requests may be not served because of violating some constraints particularly vehicle capacity and time windows constraints. On the other hand, the role of the second policy is to generate a feasible solution. In the first phase of ALNS, the probability of choosing policy 1 is the highest and the probability of choosing policy 2 is the lowest. When the algorithm progresses, the first probability becomes lower and the second probability becomes higher. At the last phase, the probability of choosing policy 1 is the lowest and the probability of choosing policy 2 is the highest. Let P 1 denotes the probability of choosing policy 1 and P 2 denotes the probability of choosing policy 2 with P 1 + P 2 = 1. P 1 and P 2 are calculated by P 2 = se nse , P 1 = 1-P 2 , where se is the number of phases executed so far and nse is the total number of phases prespecified by the algorithm.

Ruin/repair operators of ALNS

Contrary to [65], where selective (exchangeable) requests are not obligatory to be served, our problem in this thesis has two types of requests and both must be served by all carriers while each reserved request must be served by its own carrier. In the design of ruin/repair operators, we have to consider the specific features of our problem. This means that the operators must consider serving all requests. Furthermore, all reserved requests must be served before serving exchangeable requests because it is not compulsory for each carrier to serve their exchangeable requests. Actually, each exchangeable request must be allocated to the most appropriate carrier according to the policies in previous section. When the ruin operators are applied, if a route has CHAPTER 3. MULTI-CARRIERS PICKUP AND DELIVERY REQUESTS WITH TIME WINDOWS, RESERVED REQUESTS AND EXCHANGEABLE REQUESTS just one request, it will be deleted. Additionally, all of the nonempty routes are considered to insert a request when an insertion operator is used. Algorithm 2. Least profit removal operator.

1 while (number of remove < f r.rn ) 2 sort all requests in terms of profit decreasing and put in array L 3 choose a request randomly (if j is its index) j = (r U(0,1) ) 100. f r |L| 4 remove the selected requests 5 number of remove increases

Ruin operators

In this thesis, we utilize six ruin operators. In the using of ruin operators, a fraction of the solutions is removed. It means that if (rn) is the total number of requests and f r ∈ [0, 1] is a removal fraction, the number of removing requests is [ f r.rn].

Random Removal. This operator randomly chooses a subset of requests. In fact, the Random Removal operator has a strong effect in diversification.

Least profit removal. If f (so) is the cost of current solution and f (so ) is obtained cost if request i is removed, the profit of the request i in solution so is described as f (so)-f (so ). Algorithm 2, is the algorithm of least profit removal operator and the number of low profit requests are [ f r.rn].

They are removed according to Algorithm 2, because low profit requests can be reinserted in positions that are more profitable. The operator is performed randomly to avoid removing the same selected requests.

Least paid removal. This algorithm is the same as least profit removal operator with some differences. In this operator, the list L stores the prices of requests in increasing order. When the operator removes the requests with low prices and reinserts them in other positions, better solution may be achieved.

most expensive removal operator. The operator is similar to least paid removal operator; but in most expensive removal operator all requests are sorted in descending order of their cost.

Moreover, we define the difference of transportation cost with and without a request.

Shaw removal operator. This operator is introduced in [START_REF] Shaw | Using constraint programming and local search methods to solve vehicle routing problems[END_REF] and is used in [START_REF] Ropke | An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows[END_REF], [65]. Primarily, it is necessary to choose a seed request. After that, requests which are similar to the seed request based on distance, time and demand are removed. When the criterion is distance, two nodes of each request must be closed to the seed request and in choosing criterion based on time, the service starting time of pickup and delivery nodes of each request must be as same as the Price similarity removal. This operator removes the requests with the same prices. After that, a repair operator exchanges the location of the selected requests or abandons them to decrease total cost. In this operator, we use price dissimilarities between two requests. This dissimilarity measures value growing with the price differences between two requests.

Repair operators

In [65], two repair operators are applied: Basic greedy insertion heuristic and two-regret insertion.

In the current thesis, in addition to the mentioned repair operators, we also use three-regret insertion heuristic to improve the quality of the solution repaired. How to select a request to repair with two policies was discussed in previous section. Each repair operation must ensure the repaired solution is feasible, i.e., each reserved request must be served by its own carrier, all requests must be served by all carriers, vehicle capacity and time windows constraints are satisfied.

Basic greedy insertion heuristic. This heuristic inserts one by one completely removed requests to achieve the highest increase in total profit.

2-Regret and 3-Regret insertion heuristic

An obvious problem with the basic greedy heuristic is to postpone handling those hard requests that lead to construct unreasonable route at the end. The regret heuristic tries to overcome the problem by incorporating a type of look-ahead information. This means, if we do not insert the request in the current iteration, in the next iteration we may pay a lot for not having chosen it.

Regret heuristic has a grade: Each time we choose insertion of a request that holds the largest difference between its best position and second best position, which is named as 2-Regret insertion heuristic. In 3-Regret insertion heuristic, each time a request is chosen to insertion that holds the largest difference between its best position, second best, and third best positions. After each insertion, the regrets must be recomputed because some insertion positions are unavailable.

Diversification of search by simulated annealing

The goal of using simulated annealing algorithm is to prevent to be trapped in local search. The general schema of SA has been illustrated in the structure of ALNS. In comparison with the general heuristic that only accepts the improved solution, SA accepts a worse solution so -→ so with a probability e

- f (so)-f (so ) T in
, where f (so ) < f (so). The possibility is related to the problem maximization. The probability of profit decreasing depends on two factors. The first one is profit disparity, which is described by -( f (so) -f (so )) equation and second factor is temperature T in .

CHAPTER 3. MULTI-CARRIERS PICKUP AND DELIVERY REQUESTS WITH TIME WINDOWS, RESERVED REQUESTS AND EXCHANGEABLE REQUESTS

At the beginning of each run, T in is allocated to T 0 . T in is computed and if a solution has a profit 30% worse than initial solution, it will be acceptable with a (pr) probability. T in decreases after each iteration in each phase, by multiplying cooling factor co ∈ (0, 1). The cooling factor must be closed to one to avoid a premature convergence.

Local search approach

The conspicuous role of local search is to improve the results of heuristic and metaheuristic algorithms. Accordingly, at the end of each phase, we use four types of local search to achieve better results. The moves operators should assume specifications of our problem and serve all exchangeable requests. The description of neighborhoods is as follows. All feasible moves of neighborhoods are tested. The move is acceptable if an improvement is obtained; otherwise, the search continues with the next neighborhood. If there is no progress in the last results, the local search is terminated.

1. One pickup/delivery node is relocated in another place of the same route.

2. One pickup/delivery node of one exchangeable request is relocated in another place of the same route.

3. One request is relocated in another place of the same route.

4. One exchangeable request is removed from a route of a carrier and reinserted into a route of another carrier.

Hybrid genetic algorithm with simulated annealing (GASA)

Genetic algorithm (GA) is firstly proposed in [START_REF] Henry | Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence[END_REF] and it is one of the well-known metaheuristic algorithms to solve vehicle routing problems. Simulated annealing (SA), which accepts a worse solution with a probability that diminishes as the search progresses, allows the diversification of search space. The combination of GA with SA can prevent GA from premature convergence.

Hence, we propose a hybrid GA combined with SA to solve our problem. GA is inspired from nature. In GA, each solution is represented by a chromosome and the population in each iteration is composed of multiple chromosomes correspond to a set of solutions. The objective function value of the problem is evaluating the fitness of each chromosome. The reproduction process of GA is similar to that in the real world, where the next generation (population) is generated by unifying the genes of two parents from the current generation via a crossover operation. Additionally, the genes of a chromosome may be altered like gene mutation in nature. To choose parents and individuals to transfer to the next generation, the fitness of each chromosome (solution) plays a decisive role. In this process, the offspring with lower fitness are removed from the population.

In the rest of this section, all elements of GASA for multi-carriers CTP will be presented and described. The initial solutions of this algorithm, i.e., the solutions in the initial population are constructed in the same way as the insertion heuristic used in ALNS (section 3.3.1) but introducing random factors in the heuristic. It means that we have initial solution to the size of population. In each iteration of GASA, the minimum cost is updated according to the achieved cost of the latest generation. After creating new individuals by mutation and crossover operators and mixing with the current population, each solution is selected with a probability based on a simulated annealing procedure.

Solution representation

The structure of chromosome plays a vital role in order to get good results for any GA-based algorithm. The chromosome of multi-carriers CTP is defined by three vectors X , Y , and Z.

Vector X consists of all pickup and delivery nodes and its size (dimension) is |P D|. The size of vector Y is equal to the number of all requests and each component of vector Y that corresponds to a request indicates the carrier assigned to the request. The dimension of vector Z is equal to the number of all requests. In vector Z, each component indicates the index of the vehicle serving a request. It should be noted that the index of each request is the same as its pickup node index in the three vectors. The procedure for constructing a solution from a chromosome represented by the three vectors is given as follows:

Firstly, pickup and delivery nodes are chosen from vector X one by one from its first gene to its last gene. After choosing a pickup node and its corresponding request, the carrier and the vehicle (route) to serve the request are determined from vector Y and vector Z successively.

When a pickup node is assigned to a route of a carrier, its paired delivery node is also assigned to the same route of the same carrier and the precedence relation between the two nodes must be satisfied. A new route will be created if the insertion of a request (a pickup node plus its paired delivery node) into the current route leads to an infeasible solution. This means that the insertion violates time windows constraints or vehicle capacity constraint and the request cannot be served by the current route.

The coding of a solution by the three vectors mentioned above is depicted in Fig.

GASA agorithm operators

According to the chromosome structure defined for the multi-carriers CTP, we propose two crossover operators and two mutation operators for the solutions considered.

Crossover operator on vector X

Single point crossover is a suitable operator for two chromosomes of X , which has a permutation structure. By using this crossover operator, no need to apply an extra operation to make the resulted solution a feasible solution. By using this type of crossover operator in the resulted chromosome, there will be no gene repetition. To make this crossover operation, two parents chromosomes are chosen from the current population by applying the roulette wheel approach, while the crossover point is randomly chosen from all genes of vector X . The crossover operator on vector X works as follows:

To generate the first offspring, all genes of the first parent before the crossover point are transferred respectively to produce the first part of the first offspring's chromosome. To generate the second part of the first offspring after the crossover point, all genes of the second parent are compared with the genes of the first offspring already created. After ignoring repetitive genes, all non-repetitive genes are transferred to create the second part after the crossover point. The second offspring is generated in the same way as the first offspring but the roles of the two parents are swapped in the above mentioned procedure. In Fig. 3.2, the crossover operator is applied on two X vectors and their generated two offspring are given. In addition, the two arrows in Fig. 3.2 point to the crossover point.

Crossover operator on vector Y and Z

Uniform crossover is a suitable crossover operator for vector Z and Y . In this type of crossover operator creating a mask vector with one and zero genes, as illustrated in Fig. 3.3, is necessary.

The mask vector has the same size (dimension) as that of vector Z (vector Y ). A gene of an offspring is transferred from which parent depends on whether the value of the corresponding gene of the mask vector is one or zero. As illustrated in Fig 3 .3, to generate the first offspring, a gene of the first parent is transferred to the first offspring if the corresponding gene of the mask vector is zero otherwise the gene of the first offspring will be transferred from the second parent. To generate the second offspring the same operation is performed but the roles of the two parents are swapped. Since the structure of vector Y is the same as that of vector Z, the same crossover operator procedure is used.

Mutation on vector X

For vector X with a permutation structure, the mutation on vector X is made in the following way: Firstly, two distinct genes of vector X are chosen randomly. After that, one of the relocation, swap and reversion operators is chosen and applied to the two genes. This mutation operator can be applied to produce a diversified feasible solution.

1. Swap: this operator selects two components of vector X and swap their positions in the vector.

2. reverse: this operator selects two components of vector X and reverses the order of the components between the selected components.

3. relocate: this operator selects two components in vector X and relocates one of them to the front of another component.

Mutation on vectors Z and Y

The mutation applied to vector Z and Y is similar to that applied to X with some differences mentioned hereafter. The steps of the mutation over vector Z as illustrated in Fig. 3.4 are given in the following: c) Round hr to the least integer number larger than or equal to it.

2. Choose randomly l genes of vector Z.

3. Generate randomly l integer numbers between 1 and the number of all vehicles, V K.

4.

Replace the l genes of vector Z obtained in Step 2 by the l integer numbers obtained in

Step 3.

For the mutation on vector Y , the same procedure is applied except that in step 4, each gene selected in step 2 is changed with a number randomly generated between 1 and the number of all carriers, M. In Fig. 3.4, the number of mutated genes in vector Z is one and the second gene with yellow color is selected to mutate. The chromosome of the offspring is transferred from its parent's chromosome with a new value in the mutated gene.

In each iteration of GA, after sorting the new chromosomes (solutions) generated by the above mentioned GA operations, they are merged with the current population to generate the next generation. In GASA, the rule of SA is applied when transferring each offspring to an individual in the next generation. This means that, the current solutions and the solutions obtained by crossover and mutation operations are compared based on SA rule. In this way, each solution has a chance to be transferred to the next generation. To use simulated annealing in the framework of our genetic algorithm, we use the same approach of SA used previously in the ALNS algorithm we developed. At the end of each iteration of the genetic algorithm, the temperature of SA is reduced like what is done in any simulated annealing algorithm.

Algorithm 3 Pseudo-code of the ITS algorithm.

1: Set the maximum number of iterations as mni, the number of search points as nsp, the size of each tabu list stl and the number of initial solutions to be generated as nis, where mni, nsp, stl, and nis are three positive integers with nis nsp. 2: Calculate the number of possible operations no_ X, no_Y and no_Z for vector X, Y and Z respectively and set the sizes of the three tabu lists for the three vectors respectively as stl_X × no_X , stl_Y × no_Y and stl_Z × no_Z, where stl_X, stl_Y and stl_Z are three fractions between 0 and 1. 3: Initialize the three tabu lists mentioned above, which are introduced to forbidden revisiting previously explored solutions in the tabu search 4: Calculate the number of possible operations for vector X , Y and Z 5: Construct nis initial solutions 6: Sort the initial solutions in a non-increasing order of their cost value 7: Choose the nsp best solutions from the sorted list of initial solutions 8: BestSol = the cost of the best solution obtained so far 9: While the number of iterations < mni 10:

While the number of solutions (points) < nsp 11:

(the cost of the best solution in the neighborhood of the current solution) = Inf 12:

While the number of operations examined < the number of possible operations for vector X 13:

Choose an unexamined operation that moves the current solution to a new solution 14:

NewSol = the cost of the new solution 15:

If(NewSol)< BestNewSol and the operation is not in the tabu list of vector X 16:

BestNewsol=NewSol and put the operation in the tabu list of vector X 17:

End if 18:

End While 19:

While the number of operations examined < the number of possible operations for vector Y (Z) 20:

Choose an unexamined operation that moves the current solution to a new solution 21:

NewSol = the cost of the new solution 22:

If(NewSol)< BestNewSol and the operation is not in the tabu list of vector Y(Z) 23:

BestNewSol = NewSol and put the operation in the tabu list of vector Y(Z) 24:

End if 25:

End While 26:

If the number randomly generated from [0,1] < the mutation probability 27:

Execute the mutation operation 28:

End While 29:

If BestNewSol < BestSol, BestSol = BestNewSol 30: End While

Improved tabu search (ITS)

Tabu search is a local search metaheuristic propose in [START_REF] Glover | Tabu search[END_REF]. Briefly, the method explores the solution space by moving at each iteration from a solution to the best solution in a subset of its neighborhood N(s). Contrary to the classical descent method, the solution may deteriorate from one iteration to the next. Thus, to avoid any loop, some attributes of recently explored solutions are temporarily declared tabu or forbidden, even though there are better solutions in the neighbor of the current solution. The tabu list is updated in each iteration, adding a diversification in the search of the solution space. Actually, by using the tabu list the parts of solution space that were previously explored will be not considered with various techniques often employed to diversify or to intensify the search process [START_REF] Xu | Using tabu search to solve the steiner tree-star problem in telecommunications network design[END_REF]. In this section, we propose an improved tabu search (ITS) algorithm that keeps multiple solutions during the search process and uses a mutation operation in order to get a better solution quickly. On the one hand, multi-points tabu search algorithms are usually more efficient than single point ones [75], and on the other hand, some mutation operators can improve the performance of tabu search algorithm [START_REF] Jia | An improved tabu search approach to vehicle routing problem[END_REF]. The procedure of our Improved TS (ITS) algorithm is given in the following Algorithm 3, where three tabu lists containing three subsets of attributes of the solutions to be forbidden from being revisited in the tabu search are introduced and updated in each iteration. The three subsets of attributes are denoted by three vectors X , Y , and Z respectively used to represent a solution (see Section 3.3.3.1 for a description of the three vectors).

The local search operations (moves) on three vectors X,Y and Z

In tabu search based algorithms, the local search operations (moves) made in the neighborhood of a solution have a great impact on the quality of the obtained solution. In the following, we describe the local search operations made on each of the three vectors X , Y and Z representing a solution.

Operations (Moves) on vector X

The vector X has a permutation structure. The operations applied to X include swap, insertion or reversion and relocation.

Operations (Moves) on vector Y and vector Z

The vector Y and vector Z have the same structure. For this reason, the operation applied to vector Y is the same as the operation applied to vector Z. In the two vectors, a suitable change (move) is to replace the value of a component. In other words, the value of the component is changed by a number randomly generated between 1 and the number of carriers for vector Y and between 1 and the maximum number of vehicles for vector Z.

Tabu lists in the ITS

A tabu list represents a short-term memory in a tabu search algorithm. It consists of a list of previous solutions that must be avoided to revisit or a list of local search operations (moves) that must be forbidden in moving to the next solution. According to the proposed solution representation for the ITS algorithm, three tabu lists corresponding to vector X , Y , and Z respectively are introduced and updated in each iteration. Each tabu list contains a set of local search operations (moves) previously made on the corresponding vector (X , Y or Z). These operations will be forbidden when moving to the next solution in the neighborhood of the current solution. The size of each tabu list is set by considering the number of possible operations that could make on the corresponding vector. In Algorithm 3, an operation made on X , Y or Z that moves the current solution to a neighborhood solution is acceptable if it is not in the corresponding tabu list. Otherwise, the operation is not valid. If the operation is not in the tabu list and leads to a better neighborhood solution, the best solution is updated, the operation will be put in the corresponding tabu list, and the size of the tabu list is increased. In Algorithm 3, the sizes of three tabu lists are set as predefined parameters.

Numerical experiments

To evaluate the performances of our ALNS, ITS, and GASA algorithm, we applied them to solve 5 sets of instances of small to large sizes taken from the literature and compared them with the MILP solver of CPLEX 12.6 in terms of cost and computation time. The three algorithms are also compared to each other on the instances in terms of RPD. We do not compare the three algorithms with CPLEX on medium and large instances, because the latter could not even find a feasible solution after a long running time for these instances.

In the following sections, we present these instances and the comparison results. The results demonstrate the ALNS, ITS, and GASA algorithm outperform CPLEX, while the ALNS algorithm outperforms the GASA and ITS algorithms.

Instances

The instances are taken from [START_REF] Chen | Combinatorial clock-proxy exchange for carrier collaboration in less than truck load transportation[END_REF], with the reserved requests and the exchangeable requests for each carrier determined in the same way. These instances are grouped into 5 sets according to their problem sizes. The number of carriers are fixed to 3 for all instances, whereas the number of requests per carrier vary from 5 to 50 and the number of vehicles for each carrier vary from 2 to 8 for the five sets of instances. Each instance in the first set has five requests and two vehicles for each carrier. Each instance in the second set also has 2 vehicles for each carrier but has eight requests for each carrier. In the third set, there are 15 requests and 4 vehicles for each carrier.

The fourth set is composed of the instances with 30 requests and 6 vehicles for each carrier. Each instance in the fifth set comprises 50 requests and 8 vehicles for each carrier. We solved the MILP

Parameter settings

The performance of the ALNS algorithm, ITS and the GASA algorithm depends on the quality of their parameters. Some of the parameters are determined empirically and are given in Table 3.5 and Table 3.6. Other parameters are tuned by using Taguchi method, which is a popular and efficient parameter tuning technique based on fractional factorial experiments (FFE) [START_REF] Unal | Taguchi approach to design optimization for quality and cost: an overview[END_REF]. Variety of approaches, such as response surface method [START_REF] Hamid | A multi-objective facility location model with batch arrivals: two parameter-tuned metaheuristic algorithms[END_REF], [73] and Taguchi approach [71], [START_REF] Hajipour | Bi-objective vibration damping optimization for congested location-pricing problem[END_REF] are already been applied for calibration of algorithm's parameters. In this thesis, Taguchi methodology is addressed to tune the parameters of algorithms. This approach employs orthogonal arrays to handle and adapt experiences in the presence of a group of decision variables or factors [START_REF] Gs Peace | Taguchi methods, a hands on approach[END_REF]. The methodology tries to minimize the impact of noise and to achieve the optimal level of a signal factors. Since the nature of response is minimization, the smaller response is better. The following formulation expresses the signal-to-noise ratio ( S N ):

S N = -10 × log( S(Y 2 ) n ) (3.24)
Y indicates response value, n represents the number of the orthogonal arrays, and S(Y ) is the indicative objective function value.

The selected parameters of GASA and ITS to calibration are given in Table 3.7 and the parameters calibrated values are in Table 3.10 and Table 3.11 for GASA and ITS sequentially.

The selected parameters of ALNS to tune is in Table 3.8 for different size of instances and their value after calibration by Taguchi is in Table 3.9. Actually, the optimal level of each parameter in each algorithm is the highest signal-to-noise ratio. Fig. 3.5 to Fig. 3.10 show clearly the appropriate level of each parameter of the considered algorithms.

Experimental results

After the parameter calibration, we executed the ALNS, ITS, GASA, and CPLEX on all instances.

Since ALNS, ITS, and GASA algorithms contain random factors, to reduce the impacts of these random factors on their performance evaluation, each algorithm is executed three times for each instance. Then, the average cost and average computation time (in seconds) obtained by the three executions are reported. For CPLEX, since the considered carrier collaboration problem is NP-hard [66], it is very time consuming to solve optimally medium and large size instances. For this reason, we set a maximum running time for CPLEX to solve medium and large instances. The computation results are given in Table 3.12, Table 3.13, and Table 3.14. From Table 3.11, we can see, for small 3×5×2 instances, CPLEX, ALNS, ITS and GASA all could find an optimal solution. However, for some of small 3×8×2 instances and most medium to large size instances, CPLEX could not even find a feasible solution in a preset computation time, whereas our algorithms could find a feasible solution for all instances. Actually, for most instances with the number of requests more than 8, no feasible solution was obtained by CPLEX, so we compare the solutions obtained by our algorithms based on their relative gaps with the lower bound obtained by CPLEX, i.e., using the above-mentioned criteria. Our algorithms can find an optimal solution for all small 3×5×2 instances and can find a solution with the relative cost gap smaller than 3.6% for 3×8×2 instances. For medium 3×15×4 instances, our ALNS algorithm can find a solution with the gap smaller than 6%, whereas our ITS algorithm can find a solution with the gap smaller than 9.9% and GASA can find a solution with the gap smaller than 7.58%. For 3×30×6 instances, our ALNS algorithm can find a solution with the gap smaller than 12%, whereas our ITS algorithm can find a solution with the gap smaller than 14% and our GASA algorithm can find a solution with the gap smaller than 12.6%. For large 3×50×8 instances, our ALNS algorithm can find a solution with the gap smaller than 17%, whereas our ITS algorithm can find a solution with the gap smaller than 18% and our GASA algorithm can find a solution with the gap smaller than 17.4%. Moreover, our proposed algorithms are much better than CPLEX in terms of running time for medium and large instances, although the running times of the two proposed algorithms increase naturally with the size of instance and the computation time of CPLEX is smaller than those of the algorithms for small 3×5×2 instances. According to Table 3.12, Table 3.14, and Fig. 3.11 ALNS has cost and computation time smaller than those of ITS and GASA respectively for all instances, therefore ALNS outperforms ITS and GASA. This may be because various ruin/repair operators, adaptive mechanism, and SA are used in ALNS, which makes it able to search diversified regions in the solution space.

Relative percentage deviation (RPD) to compare algorithms

There are two ways to compare the algorithms. One is to classify the samples in small, medium, and large sizes and then compare the algorithms in each category. The second way is to remove the effect of problem size by utilizing an index. RPD is an indicator calculated by the difference between the best solution of an algorithm in terms of cost or profit and the best solution achieved In this thesis, we calculate the RPD of each algorithm after three executions. According to the formulation of RPD, an algorithm is efficient if it has small amount of RPD. Table 3.15 and Fig. 3.11 illustrate the results of RPD over ALNS, GASA, and ITS. According to the results, ALNS has better RPD and it outperforms the other two algorithms. Additionally, GASA has better RPD in comparison with ITS. Their statistical analysis is illustrated in Table 3.16. According to Table 3.16 there is not significant difference between GASA and ITS. Finally, the algorithms are also statistically analyzed according to obtained solutions via analysis of variance (ANOVA) tests [START_REF] Hajipour | Bi-objective vibration damping optimization for congested location-pricing problem[END_REF].

The procedure of ANOVA including F-test value and also P-value on RPD is summarized in Table 3

Instance Number Gap ALNS Gap ITS Gap M ILP Gap G AS A 3×5×2 instances 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3×8×2 instances 0.

Conclusion

In

MULTI-PERIODS BID GENERATION PROBLEM WITH PICKUP AND DELIVERY, TIME WINDOWS, PROFITS, AND RESERVED REQUESTS

I n the real world applications, carriers usually plan their pickup and delivery operations and use of vehicle resources in advance (several days ago) in a rolling horizon [START_REF] Wang | A rolling horizon auction mechanism and virtual pricing of shipping capacity for urban consolidation centers[END_REF], [START_REF] Daniel Handoko | An auction mechanism for the last-mile deliveries via urban consolidation centre[END_REF].

This requires that each carrier considers multi-periods (days) when it determines which transportation requests to bid and serve in each period (day). Moreover, requests open for bid (requests to be exchanged among carriers) may span across multi-periods (days). That is, instead of fixing a day to serve each selective request, each request is allowed to be served within a service day window consisting multi consecutive days. For example, goods ordered on-line by a customer on Monday in e-commerce is asked to deliver to the customer's home within three days from Tuesday to Thursday. This gives rise a multi-periods combinatorial auction (CA) problem.

As a result, the bid generation problem of each carrier in such auction also involves multi-periods, where a bid is a combination of transportation requests over multi-periods [62].

In this chapter, a multi-periods Bid Generation Problem (BGP) for a carrier is considered.

In the problem, there are two different types of requests, reserved requests of the carrier and selective requests. The carrier is committed by contracts with its shippers to serve all reserved requests by itself. The selective requests are offered by other carriers and are open for bid by the carrier. Each request has a pickup and delivery request with a pickup node, a delivery node, a pickup/delivery quantity, and two time windows. Period window specifies the earliest period and the latest period that each request must be served while time window shows the earliest and latest service time and is allocated to both pickup and delivery nodes. In addition, each selective request is associated with a profit that is the price for serving the request provided by a shipper. By including periodic concept in CA, the carrier can plan its transportation operations in advance and in a rolling-horizon. A carrier must make two important decisions in the BGP:

Which requests are chosen to bid and serve in their service period windows and how the routes are constructed to maximize its total profit. This leads to a new periodic pickup and delivery problem with time windows, profits, and reserved requests. So, this problem is a different problem from the problem presented in [65] that considers single period BGP. According to [START_REF] Wang | Collaborative transportation planning of less-than-truckload freight[END_REF], the present problem is NP-hard and it is impossible to get feasible solutions for large instances by using a commercial solver like CPLEX. Hence, a hybrid approach that combines a genetic algorithm and simulated annealing (GASA) is proposed to solve the problem. The GASA adopts a problem-specific chromosome structure, crossover, and mutation operations well adapted to the chromosome structure. This algorithm utilizes the specifications of population-based algorithm and single point algorithm to diversification and intensification of the solution sequentially. For the purpose of comparison, we utilize Biogeography-Based Optimization algorithm (BBO) that is a population-based algorithm and its specifications are close to the GA and its operation is over the population of solutions to reach the best solution. By comparing GA and BBO, each chromosome in GA, which is considered as an individual with fitness value is habitat with suitability index that is called HSI (Habitat Suitability Index). Usually, a habitat with high HSI is acceptable and yields better solutions. The numerical results demonstrate the proposed algorithms can find a feasible solution in a reasonable computation time for large instances.

The rest of the chapter is organized as follows. Section 4.1 is devoted to literature review.

A detailed description of a mathematical model for the studied problem is given in Section 4.2.

In section 4.3, the GASA and BBO algorithms are described. In Section 4.4, detailed numerical results of solving the model by GASA, BBO and CPLEX solver on randomly generated instances are presented and compared. The final section, Section 4.5, concludes this chapter.

Literature review

The considered problem in this chapter is a bid generation problem with multi-periods in collaborative transportation. The bid generation problem (BGP) is a key decision problem for auction-based decentralized planning approaches in CTP, which is considered from the perspective of each carrier. The BGP can also be considered as the request selection problem. In [START_REF] Wang | Combinatorial bid generation problem for transportation service procurement[END_REF] authors study a carrier's BGP in the context of TL transportation service procurement. In this paper, the focus is on the bundling method when an OR bidding language is used. They firstly define the bidder's optimality criterion of combinatorial bids. Then two heuristics are developed and compared, one is based on a fleet assignment model and the second is based on nearest insertion method. In [63] the carrier's optimal BGP is considered in combinatorial auctions for transportation procurement in TL transportation. Carriers employ vehicle routing models to identify the sets of lanes to bid for based on actual routes. Both column generation and Lagrangian based techniques are used for solving the carrier optimization model and promising results are reported. An exact strategy and two heuristic strategies have been proposed in [START_REF] Buer | An exact and two heuristic strategies for truthful bidding in combinatorial transport auctions[END_REF] for bidding on subsets of requests. The shows that it is sufficient for a carrier to bid on each elementary request combination in order to guarantee the same result as bidding on each element of the power set of tendered requests.

In [63] column generation and Lagrangian relaxation approaches are used in transportation problem to solve the BGP in combinatorial auction.

Our work in this chapter is related to the work in [65]. Both assume the BGP of a carrier, but the BGP considered in this thesis involves multi-periods. There are two interesting studies in multi-periods BGP [START_REF] Wang | A rolling horizon auction mechanism and virtual pricing of shipping capacity for urban consolidation centers[END_REF], [START_REF] Daniel Handoko | An auction mechanism for the last-mile deliveries via urban consolidation centre[END_REF]. In these papers, each carrier considers multi-periods (days) when it determines which transportation requests to bid and serve in each period (day). Moreover, requests open for bid may span across multi-periods (days).

Other works related to ours include studies on the Oriented Problem (OP) and Team Orienting Problem (TOP). Selective TSP or TSP with profits is known as OP [61], [37]. A survey article in OP is presented in [34]. Multi-vehicle routing problem with profits is called Team Orienting Problem (TOP). In [START_REF] Butt | A heuristic for the multiple tour maximum collection problem[END_REF], [START_REF] Chao | The team orienteering problem[END_REF] authors focus on TOP by considering multi-tours maximum collection problem and multi-tours VRP with profits. Full truckload VRP with profits is studied in [64].

In the article, all demands are assigned to outsource companies if they cannot be allocated to resources. To solve large instances, hybrid genetic algorithm is applied. An interesting study in In [60] TOP with time windows is considered. The solution method in the paper is a granular variable neighborhood search. Multi-periods orienting problem is presented in [START_REF] Tricoire | Heuristics for the multi-period orienteering problem with multiple time windows[END_REF]. In the problem different time windows are considered in terms of different serving days. Periodic VRP with unpaired pickup and delivery is proposed in [START_REF] Divya | Food Rescue and Delivery[END_REF]. In each period of the problem, the demand from a pickup node can be delivered to single or multiple delivery nodes. Therefore, the authors called the problem unpaired VRP with pickup and delivery. Different problems in periodic VRP is proposed in [START_REF] Coene | On a periodic vehicle routing problem[END_REF]. Different solutions are suggested in the paper to solve the problem. Multiperiods vehicle routing problem with due dates is investigated in [START_REF] Archetti | Multi-period Vehicle Routing Problem with Due dates[END_REF]. In the paper, customers have to be served between delivery time and due date, otherwise they have to be paid a delay cost. Another type of periodic VRP is flexible periodic VRP is examined in [START_REF] Archetti | The Flexible Periodic Vehicle Routing Problem[END_REF]. In this type of VRP, each customer is served in different periods with the same demand. This type of periodic VRP is considered as a special case of inventory routing problem (IRP). In [START_REF] Cantu-Funes | Multi-Depot Periodic Vehicle Routing Problem with Due Dates and Time Windows[END_REF] periodic VRP with time windows is reported. In the paper, a mathematical model is presented and greedy randomized adaptive search is used to solve the model. There are little works in the multi-periods VRP with time windows and the periodic VRP with pickup and delivery with time windows is not considered in the literature. An article in the multi-periods VRP with time windows is in [START_REF] Cordeau | A unified tabu search heuristic for vehicle routing problems with time windows[END_REF] that the authors present general mathematical model to different VRP problems. The solution approach to solve the model is tabu search.

VRP

Formal definition and mathematical model

In this problem, we consider a carrier who wants to determine which requests to bid (select)

among all requests open for bid (offered by all carriers) in a combinatorial auction to maximize its own profit by solving a bid generation problem. Since the carrier plans its transportation operations in advance and in a rolling horizon way as mentioned in the introduction, this bid generation problem involves multi-periods. We consider the problem in the less-than-truck load transportation, where each transportation request is a pickup and delivery request with time windows, reserved requests, and selective requests are involved as each request is associated with a profit which is the revenue to serve the request. Formally, the multi-periods bid generation problem with pickup and delivery requests, time windows, selective requests, reserved requests, and profits can be defined on a directed graph G = (V , E), where V is the set of all nodes comprising all pickup nodes, delivery nodes, and the depot node of the carrier. In the graph, E is the set of all edges. The node set is defined as V = {0, ..., 2n + 1}, where n represents the number of requests, 0 and 2n+1 denote the depot of the carrier, i and n + i represent the pickup and delivery nodes of request i, i = 1, 2, . . . , n. Let W denotes the set of nodes excluding the depot node. As mentioned before the problem is multi-periods BGP with the number of periods denoted by H. In the problem, the carrier has a finite fleet of homogeneous vehicles whose index set is given by K = {1, 2, . . . , V K}, where V K is the maximum number of vehicles. The capacity of each vehicle is denoted by Q and the load of each vehicle cannot exceed its capacity. The set P = {1, 2, . . . , n} is the set of pickup nodes of all requests and the set of all delivery nodes is given by D = {n + 1, .., 2n}.

In our model, each request i has its pickup node i and delivery node i + n. The demand of the pickup node of request i is denoted by d i , while the demand of the delivery node of the same request is denoted by d i+n , as d i+n = -d i . The delivery node of each request must be visited after its pickup node on the same route. The set of all requests is denoted by R, where R = ( l∈H R l r ) R s . R l r is the set of reserved requests that must be served in period l and R s is the set of selective requests. Each selective request has a service period window and two time windows. The service period window determines in which periods the selective request can be served. The two time windows determine at which times in each period the pickup and delivery nodes of a request can be visited by a vehicle that serves the request. Both selective and reserved requests are associated with two types time windows, whereas only selective requests are associated with a service period window (the period in which each reserved request must be served is prespecified).

The time window of pickup node i and delivery node i + n of request i are denoted by [e i , l i ] and [e i+n , l i+n ], respectively. The service period window for each selective request i is represented by [E i , L i ]. Each reserved request i ∈ R l r must be served in its prespecified period l, l ∈ H. The traveling time and transportation cost between two nodes i and j are assumed to be same and they are denoted by t i j and c i j respectively. The maximum duration of each route i is limited by T. The multi-periods bid generation problem can be formulated as a mixed-integer linear programming model. In the model, parameters BM i j = l j -e i is used to formulate linearly time windows constraints while C i = Q + d i is used in capacity constraints. The decision variables of the model include binary variables, x i jkh and y ikh . Two real variables U ikh and CV ikh are defined as follows:

x i jkh =    1
if and only if in period h vehicle k visits directly node j after node i 0 Otherwise

y ikh =    1 if
k∈K i∈D;i =(2n+1) h∈H x i(2n+1)kh ≥ 1 (4.3) k∈K y ikh = 1 ∀l ∈ H, ∀i ∈ R l r (4.4) h∈[E i ,L i ] k∈K y ikh ≤ 1 ∀i ∈ R s (4.5)
j∈V , j =i,0

x j(n+i)kh = y ikh ∀i ∈ P, k ∈ K, ∀h ∈ H (4.6)

j∈V , j =i,2n+1

x i jkh = y ikh ∀i ∈ P, k ∈ K, ∀h ∈ H (4.7)

U ikh + t i,(n+i) + s i ≤ U (n+i),kh ∀i ∈ P, k ∈ K, ∀h ∈ H (4.8) U jkh ≥ U ikh + t i j + s i -BM i j (1 -x i jkh ) ∀i ∈ V , k ∈ K, ∀h ∈ H, ∀ j ∈ V (4.9) e i y ikh ≤ U ikh ≤ l i + (1 -y ikh ) j∈V BM i j ∀h ∈ H, ∀i ∈ V , ∀k ∈ K (4.10) U ikh + t i j + s i -BM i j (1 -x i jkh ) ≤ T ∀i ∈ V , k ∈ K, ∀h ∈ H, ∀ j ∈ {0} (4.11) C V ikh + d i -C i (1 -x i jkh ) ≤ CV jkh ∀i ∈ V , k ∈ K, ∀h ∈ H, ∀ j ∈ V (4.12) m ax{0, d i } ≤ CV ikm ≤ min{Q,Q + d i } ∀i ∈ V , k ∈ K, ∀h ∈ H (4.13) x i jkh ∈ {0, 1} ∀i, j ∈ V , ∀k ∈ K, ∀h ∈ H (4.14) U ikh ≥ 0 ∀i ∈ V , ∀k ∈ K, ∀h ∈ H (4.15) C V ikh ≥ 0 ∀i ∈ V , ∀k ∈ K, ∀h ∈ H (4.16)
y ikh = 0 for any i ∈ R s , ∀k ∈ K, for any h ∉ (E i , L i ) and y ikh = 0 for any i ∈ R rl,l =h (4.17)

The objective function represents the total profit of the carrier, which is equal to the difference between the total payments of serving requests in all periods and the total transportation cost.

Metaheuristic approaches to solve multi-periods bid generation problem

In section 4.2, we have presented the MILP model to multi-periods BGP. Since existing commercial solvers are not powerful enough to solve the large size of PDPTW in a reasonable time, we apply GASA and BBO to solve this problem.

Initial solution construction procedure

The presented initial solution for the problem in this chapter is close to the initial solution structure in Chapter 3 (section 3.3.1) with a small difference in step 3. In the proposed hybrid genetic algorithm with simulated annealing (GASA), the size of population determines the number of initial solutions to construct. As described in the previous sections, all reserved requests must be served in their predetermined periods while some selective requests may be not served when they are not profitable. Profitable selective requests may be served in the periods within their service period windows.

The three ways are given in the following:

1. Only the reserved requests are served.

2. All reserved requests are served firstly and then selective requests are served.

3. All reserved requests must be served first and selective requests are served only if its assigned period is not zero (it is explained in section 4.3.2.1). That is, if the period assigned to the request is zero, it will be not served.

If the probability of choosing each three ways to construct an initial solution is denoted by α 1 , α 2 and α 3 , respectively, then α 1 +α 2 + α 3 = 1.

Hybrid genetic algorithm with simulated annealing (GASA)

The applied GASA in this section is the same as GASA in Chapter 3. It means that in this algorithm, a chromosome represents each solution and the population in each iteration is composed of multiple chromosomes. All components of GASA for multi-periods BGP with pickup, delivery and time windows will be explained in the rest of this section. In each iteration of GASA, the maximum profit is updated thanks to the obtained profits in the latest generation. SA is applied to each solution of the present population. Each solution is selected with a probability based on a simulated annealing procedure.

Solution representation in GASA

The chromosome of multi-periods BGP is defined by three vectors X , Y , and Z. Vector X includes all pickup nodes and delivery nodes and its dimension is |P ∪ D| as the index of each request is the same as its pickup node index in the three vectors. What's more, each selective request must be served in a period within its service period window. Thus, an extra period is introduced to indicate a not served selective request. This extra period is referred to period 0. The size of vector Y is equal to the number of all requests and each component of vector Y indicates the period assigned to a request. Since a selective request is not necessarily to be served, it will not be served if it is not profitable. The dimension of vector Z is equal to the number of all requests. In vector Z, each component indicates the index of the vehicle serving a request. A simple instance (example) is given in the following to help the understanding of chromosome structure, where the data of this instance are given in determine all pickup and delivery nodes are visited by each route in each period. We put all these pickup and delivery nodes in a list we call if list L. To constrcut a route, a node is selected from the beginning of the list. If the node is a pickup node, it will be added to the route. Otherwise, if the node is a delivery node, it is added to a route only if its corresponding pickup node has been added to the route previously. Once a node from list L is added to the route, it will be deleted from the list. The following procedure explains the schedule repair function applied for generating routes in day 1.

1. In day 1 and route 1, there are 4 pickup/delivery nodes, which constitute the list L.

2. A selected node from the beginning of list L is inserted into a route R if it is a pickup node or its pickup node has been inserted in route R previously. For example, L(1) = 6 is a delivery node because its index is larger than the number of requests. When it is chosen, all nodes of route R are checked. If its corresponding pickup node has been inserted previously into list R, the node 6 is inserted into the route as well. Otherwise, it will be ignored. The next node is L(2) = 3, which is a pickup node, so it is inserted into route R.

In the next step after removing node 3 from list L, it is checked from the beginning to choose the next node to insert into route R. The node 6 is a delivery node and its pickup node, node 2, is not in the route R. Consequently, the component which is chosen from the list L as a next node id node 7. The node 7 is a delivery node and its corresponding pickup node, node 3, has been inserted previously in route R. Therefore, node 7 is inserted to list R and deleted from list L. Generally, after deleting a node from the list L and inserting in the list R, the list L will be explored from the beginning to choose a node to insert into the route R.

After deleting node 7, the list L is checked from the beginning again. Since the pickup node of 6 has not been inserted previously into route R, exploring the list L continues. By exploring the list L from the beginnin, there is a single node, node 6, which is the corresponding delivery node of node 2. Because its pickup node, node 2, has been added to the list R previously, so the node 6 is inserted in the route list R.

The same procedure is applied to construct the routes in other days. The list L and route R for first day are given below:

GASA algorithm operators

The GASA chromosome in this chapter and Chapter 3 has the same structure. In the previous chapter, there are multi-carriers, which have been illustrated by vector Y . In this chapter, there are multi-periods instead of multi-carriers and they can be illustrated by the same vector. The other two vectors with the same structure, vector X and Z, can be applied to the GASA in this chapter. In Chapter 3, each component of vector Y is the suitable carrier to serve each request. In this chapter, each component of vector Y is the suitable period to serve a request.

According to the structure of each solution for the studied problem, two crossover operators and two mutation operators are proposed. In the rest of this section, these operators are summarized.

The comprehensive and complete descriptions of operators are in Chapter 3.

Crossover operator of vector X

In the suggested chromosome structure to the GASA, vector X has a permutation structure and a single point crossover is applied. In fact, this crossover operator avoids node duplications in the offsprings.

Crossover operator of vector Y and Z

The uniform crossover is a suitable crossover operator to the vectors Z/Y . In the uniform crossover, a mask vector with zero and one entries (genes) and the same size as K/Y is generated.

The value of each offspring's gene is produced according to the value of the corresponding gene in the mask vector and the component of gene in the parent.

Mutation operator of vector X

To have a diversified feasible solution, a mutation operator with the following two steps is applied to vector X with the permutation structure.

1. Choose randomly two genes of vector X .

2. Choose randomly one of the insertion, swap, and reversion operations. Execute the selective operation on the selective genes.

Mutation over vectors Z and Y

The mutation over vector Z is realized in three steps. In the first step, the number of mutated genes of vector Z is determined randomly and denoted by l. The number of mutated genes are obtained in the following way: An integer number h is randomly generated between 1 and dim[Z],

where dim[Z] is the number of genes in vector Z and V K is the total number of vehicles. This number is then multiplied by a mutation rate r, leading to hr. By rounding hr to the smallest integer number larger than or equal to hr, the number l is finally obtained. In the second step, l genes are randomly selected from Z. In the third step, for each selective gene of Z, an integer number is randomly generated between 1 and V K, and the gene in Z is changed to this value.

The mutation over vector Y is the same procedure as the mutation over vector Z.

Simulated annealing algorithm in GASA

Most heuristic algorithms only accept an improved solution, whereas simulated annealing gives a chance to worse solutions, which accepts a worse new solution with a probability. The new solution acceptance probability is given by e

- f (s)-f (s ) T 0
, where f (s ) is the objective value of the new solution and f (s) is the objective value of the current solution and f (s ) < f (s). The acceptance probability depends on both the temperature parameter T 0 and the profit decrease f (s) -f (s ) while the temperature is decreased at the end of each iteration. The temperature reduction is performed by multiplying T 0 with a cooling factor co ∈ (0, 1). To attain a slow cooling, the cooling factor must be set close to one. At the beginning of the execution of the GASA algorithm the temperature parameter, T 0 , is set to T in and a solution with profit 30% lower than the initial solution is accepted with a given possibility pr. In GASA, to produce the next generation solutions, at the end of each GA iteration, the solutions generated by crossover and mutation are sorted and merged with the current population. GASA utilizes the SA rule to determine whether each solution in the sorted list becomes a solution (chromosome) in the next generation. In other words, to give an opportunity being selective to each solution, SA rule is used to compare the solutions in the current population and the solutions obtained by crossover and mutation. In the same way as in simulated annealing algorithm, the temperature of SA is decreased at the end of each iteration in our GASA algorithm.

Biogeography-based optimization algorithm (BBO)

BBO is a meta-heuristic algorithm inspired by Biogeography Science to explore the solution space. In [START_REF] Simon | Biogeography-based optimization[END_REF], the theory of Biogeography is used to solve the optimization problems according to this fact that Biogeography studies the manner of organisms during time and space. Simon's proposed algorithm like GA is a population-based algorithm as its operation is over the population of solutions to search the best solution. By comparing GA and BBO, each chromosome in GA, which is considered as an individual with fitness value is habitat with suitability index that is called HSI (Habitat Suitability Index). Usually, a habitat with high HSI is acceptable and yields better solutions. In the algorithm, species migrate from the regions with high HSI to places with

METAHEURISTIC APPROACHES TO SOLVE MULTI-PERIODS BID GENERATION PROBLEM

low HSI to upgrade these regions. Emigration and immigration are two operators to improve solutions and maximize the HSI, where the first operator is applied on the regions with high HSI and the second one is used in opposite side. Solution structure of BBO is called habitat and its representation is same as individual in GASA. In [START_REF] Habib | A new biogeography-based optimization (BBO) algorithm for the flexible job shop scheduling problem[END_REF], two algorithms are compared and presented in Table 4.4.

Selection strategy

The main difference between GASA and BBO is the modification of solutions in diverse iterations instead of their omission. Actually, the main goal of BBO in this step is determining the regions, which needs corrections along with highlighting solutions to use their attributions. Selection methods in BBO are divided to two parts; first migration operators, second mutation. The migration operator of BBO is like GASA crossover operator, but BBO migration operator is performed between immigrant habitat and emigrant one. In the current sections, operators are described. Like GASA, the most important part of BBO is solution representation. H i is the solution structure of BBO, called habitat, is the same as an individual structure of GASA (explained as in section 4.3.2).

Selection approach of migration operators

Overall, there are two decisions. Does the special place (H i ) alter or not? Produced random number should be compared with immigration rate (λ i ). Setting region (H j ) as an origin of conducting attributes to Hi will be the next step. Roulette wheel is an appropriate technique that is implemented at the emigration rate (µ j ). In the current paper, fulfilling BBO mutation operator is the same as GASA mutation operator. In reality, the output of this phase determines whether the considered region has to be mutated or not.

2. Migration operator is used to the modification of solutions and its idea related to the theory of migration in species. In this process, each H j solution is selected according to its immigration and emigration rate to achieve or share attributes, respectively. There is necessary to mention, SIV in BBO algorithm is the equivalent with a gene in chromosome structure of GASA. If SIV is a solution attribute, the following inequality shows the mentioned possible relation H i (SIV ) ←-H j (SIV ). Figure 4.2 illustrates the mechanism in translation between both rates in relation to species plenty [START_REF] Simon | Biogeography-based optimization[END_REF]. Indeed, interaction between high and low HSI as mentioned previously causes emigration rate to reduce due to species increasing in habitat; as a result of this increment, immigration rate decreases and the emigration rate rises. In Fig. 4.2, E and I demonstrate maximum immigration and emigration rates respectively in which most of the time their values are 1. S max is the maximum number of species that a habitat can accept and S 0 is the balance point, where two rates are equal. Although in Fig. 4.2 rates show it can be used for the linear model, the non-linear model also can be discussed [START_REF] Simon | Biogeography-based optimization[END_REF].

Accordingly, after calculating HSI, immigration and emigration rates are calculated by inequalities (4.18) and (4.19). K i is the rank of each solution after sorting them based on HSI insofar as the better solution has high rank and consequently larger k i .

λ i = I(1 - k i n ) (4. 18
)
µ i = E( k i n ) ( 4

Experimental results

To evaluate the performance of the proposed two metaheuristic algorithms, we applied them to solve 8 sets of instances of small to large sizes taken from the literature and compared them with the MILP solver of CPLEX 12.6 in terms of profit and computation time. In the following sections, we present these instances and the comparison results. The results display both GASA and BBO algorithm remarkably outperform CPLEX, while the GASA algorithm outperforms the BBO algorithm.

Instances

The instances are taken from [65] with the same reserved requests, selective requests, the coordinates of each node, the demand and time windows of each request. 56 instances are generated in small size (n ∈ {6, 8, 10, 20}), medium size (n ∈ {30, 40, 50}) and large size (n ∈ 100).

Conclusion

In In the problem, each selective request is associated with a profit, which is the price for serving the request provided by a shipper and associated with a period window that specifies the earliest period and the latest period the request must be served. In each period, the carrier has a set of reserved requests and must be served by the carrier itself. Each request has a pickup node and a delivery node, and each node has a time window which specifies the earliest time and the latest time at which the node must visited by a vehicle in each period. By including periodic concept in CA, the carrier can plan its transportation operations in advance and in a rolling-horizon way.

The objective of the decision problem for the carrier is to determine which selective requests to serve in each period in addition of reserved requests and feasible routes to serve the reserved and selected requests to maximize its total profit. For this NP-hard problem, a mixed-Integer Linear Programming (MILP) model is formulated and two metaheuristic algorithms are proposed to solve the model: One is Genetic algorithm combined with Simulated Annealing (GASA) and the other is Biogeography-Based Optimization algorithm (BBO). The GASA and BBO are evaluated on 30 instances with 6-100 requests. The computational results show the two algorithms significantly outperform CPLEX solver, not only in solution quality but also in computation time, and the performance of GASA is better than BBO in terms of the two criterions. are demanded and valued [START_REF] Hu | Transportation service procurement problem with transit time[END_REF]. There is however, evidence supporting a move towards more partnerships and horizontal cooperation [START_REF] Schmoltzi | Horizontal cooperations between logistics service providers: motives, structure, performance[END_REF]. In fact, during the last two decades collaboration within the supply chain management receives a great deal of attention [START_REF] Barratt | 129 BIBLIOGRAPHY Understanding the meaning of collaboration in the supply chain[END_REF].

MULTI-PERIOD BID GENERATION PROBLEM

For companies, besides minimizing all costs, shippers are interested in reducing the delivery lead time. Reducing delivery lead time has two benefits. At first, shorter delivery lead time makes supply chain management more agile, since orders are processed faster. Thus, it improves the ability of shippers to compete in the industry. Another benefit of shorter delivery lead time is choosing the carriers according to geographic factors [START_REF] Hu | Transportation service procurement problem with transit time[END_REF]. In many procurements of transportation services, although cost is an important consideration in evaluating bids, shippers care about delivery lead time when evaluating bids submitted by carriers [START_REF] Ghosh | Scoring auctions: A brief survey[END_REF].

Although the delivery lead time is an important criterion in the procurement of a transportation service, its consideration in BGP has not been well addressed in the literature. Therefor, we focus on this topic in this chapter. Actually, in this chapter we consider a bid generation problem in a combinatorial auction for carrier collaboration, where each carrier determines the requests to bid for solving a BGP. After receiving the bids from all carriers, the auctioneer (an auction platform) determines the winning carriers and their winning bids. The auctioneer has An auxiliary variable used in the linearizion of model.

with two nodes, a pickup node i and a delivery node n + i, where n represents the number of requests and the demand of a pickup node is equal to the demand of its corresponding delivery node. The delivery node of each request must be visited after its pickup node on the same route.

The number of customers, their locations, the capacity of each vehicle, and the fleet of vehicles are predefined. There are other assumptions to this problem like the quantity of pickup/ delivery is smaller than vehicle capacity and all vehicles are homogeneous. The cost of satisfying customers' demands depends on the vehicles' total travel distances. Each selective request has a service period window and two time windows for pickup and delivery respectively. The service period window defines the periods when each selective request can be served and the two time windows determine at which times in each period the pickup node and the delivery node of the request can be visited by a vehicle that serves the request, for instance morning and afternoon windows separated by a lunch break. Both selective and reserved requests are associated with two time windows, whereas only selective requests are associated with a service period window (the period in which each reserved request must be served is prespecified). If a selective request is served, the most appropriate period to serve it should be determined. In addition, each request i is associated with a weight α i , which can be interpreted as the penalty cost for one time unit longer of delivery lead time.

The multi-period bid generation problem can be formulated as a mixed-integer linear programming model. The aim of the problem is to serve all reserved requests in their predefined period and to determine which selective requests should be served to improve the total profit.

The parameters of the problem are listed in Table 5.1, while the decision variables employed are in Table 5.2. Hence, the single objective mathematical model of the multi-period BGP is given as follows:

max( i∈R h∈H k∈K p i y ikh -h∈H i∈V j∈V k∈K c i j x i jkh -j∈R s α j ( h∈[E i ,L i ] k∈K y jkh )) subject to:

j∈V ; j =i x jikh - j∈V ; j =i x i jk = 0 ∀i ∈ W, ∀k ∈ K, ∀h ∈ H (5.1)

PROBLEM DESCRIPTION AND MATHEMATICAL MODEL

k∈K j∈P; j =0 h∈H x 0 jkh ≥ 1 (5.2)

k∈K i∈D;i =(2n+1) h∈H x i(2n+1)kh ≥ 1 (5.3) k∈K y ikh = 1 ∀h ∈ H, ∀i ∈ R r l (5.4) h∈[E i ,L i ] k∈K y ikh ≤ 1 ∀i ∈ R s (5.5)
j∈V , j =i,0

x j(n+i)kh = y ikh ∀i ∈ P, k ∈ K, ∀h ∈ H (5.6)

j∈V , j =i,2n+1

x i jkh = y ikh ∀i ∈ P, k ∈ K, ∀h ∈ H (5.7)

U ikh + t i,(n+i) + s i ≤ U (n+i),kh ∀i ∈ P, k ∈ K, ∀h ∈ H (5.8) U jkh ≥ U ikh + t i j + s i -BM i j (1 -x i jkh ) ∀i ∈ V , k ∈ K, ∀h ∈ H, ∀ j ∈ V (5.9) e i y ikh ≤ U ikh ≤ l i + (1 -y ikh ) j∈V BM i j ∀h ∈ H, ∀i ∈ V , ∀k ∈ K (5.10) U ikh + t i j + s i -BM i j (1 -x i jkh ) ≤ T ∀i ∈ V , k ∈ K, ∀h ∈ H, ∀ j ∈ {0} (5.11) C V ikh + d i -Q(1 -x i jkh ) ≤ CV jkh ∀i ∈ V , k ∈ K, ∀h ∈ H, ∀ j ∈ V (5.12) m ax{0, d i } ≤ CV ikm ≤ min{Q, d i } ∀i ∈ V , k ∈ K, ∀h ∈ H (5.13) x i jkh ∈ {0, 1} ∀i, j ∈ V , ∀k ∈ K, ∀h ∈ H (5.14) U ikh ≥ 0 ∀i ∈ V , ∀k ∈ K, ∀h ∈ H (5.15) CV ikh ≥ 0 ∀i ∈ V , ∀k ∈ K, ∀h ∈ H (5.16)
y ikh = 0 for any i ∈ R s , ∀k ∈ K, for any h ∉ (E i , L i ) and y ikh = 0 for any i ∈ R rl,l =h (5.17)

y jkh ≥ h × y jkh -E j ∀ j ∈ V , ∀k ∈ K, ∀h ∈ H (5.18)
y jkh ≥ 0 ∀ j ∈ V , ∀k ∈ K, ∀h ∈ H (5.19)
The objective function corresponds to the score of a bid of the carrier, which is equal to the difference between the total payments of serving requests in all periods, the total transportation cost and the penalty costs of delivery lead-time. The considered score, is formulated as the single objective function, in this model. Constraint (5.1) ensures that when a vehicle arrives at a node in a period, it must leave in the same period. Constraints (5.2) and ( 5.3) signify that each vehicle leaves its depot of carrier in a period must return to it in the same period. Equation (5.4) implies that each reserved request must be served in its predetermined period. Equation (5.5) indicates that each selective request can be either served in a period within its service period window or not served. Constraints (5.6) and (5.7) guarantee if a request is served in a period, its delivery node must be visited after its pickup node with the same vehicle in the same period. Equations Except for costs, shippers are also concerned with transit time (delivery lead time); shorter transit time represents better transportation service. It is possible to formulate the multi-period BGP as a bi-objective problem, on the one hand, the profit is maximized and on the other hand the delivery lead time is minimized. It means that one of the objective functions is the maximization of the total profit and the other one is the minimization of weighted delivery lead time for all requests. Consequently, in the previous single objective model, the weighted delivery lead time of all requests will be considered as a second objective function.

First objective function: max( i∈R h∈H k∈K p i y ikh -h∈H i∈V j∈V k∈K c i j x i jkm )

Second objective function:

min j∈R s α j ( h∈[E i ,L i ] k∈K y jkh ) 5.

METAHEURISTIC APPROACHES TO SOLVE A SINGLE OBJECTIVE MULTI-PERIOD BID GENERATION PROBLEM WITH CONSIDERATION OF DELIVERY LEAD TIME

Metaheuristic approaches to solve a single objective multi-period bid generation problem with consideration of delivery lead time

In the literature, two approaches are usually used to solve complicated multi-objective optimization problems. In the first approach, a multi-objective problem is transformed into a single-objective optimization using some multi-criteria decision making (MCDM) techniques presented in [START_REF] Hwang | Multiple objective decision making-methods and applications: a state-of-the-art survey[END_REF]. In the second approach, multi-objective algorithms such as non-dominated sorting genetic algorithm (NSGA-II) and non-dominated ranking genetic algorithm (NRGA) are directly employed to find a set of optimal solutions called Pareto optimal solutions in a single run [START_REF] Al Jadaan | Parametric study to enhance genetic algorithm performance, using ranked based roulette wheel selection method[END_REF].

The multi-period bid generation problem with pickup and delivery requests, time windows, profits, reserved requests, and delivery lead time is a NP-hard vehicle routing problem [65].

Consequently, it cannot be solved optimally for large instances, and metaheuristic algorithms are required to solve these types of problems. In this chapter, we solve the problem in both single objective perspective and bi-objective perspective. Firstly, the single-objective problem is solved by using GASA and ITS which are described in Chapter 3. Secondly, the multi-objective problem is solved using NSGA-II and NRGA.

For the single objective multi-period bid problem with the consideration of delivery lead time, GASA and ITS used to solve it are similar to those presented in Chapter 4, except that the delivery lead time of each request is considered in the objective function of the problem. For this reason, we will not present the two algorithms again in this chapter. Besides, NSGA-II and NRGA that are used to solve the bi-objective problem are derived from Multi-Objective Genetic Algorithms, so their chromosome is the same as chromosome of GASA which is described in Chapter 4.

Metaheuristic approaches to solve a bi-objective multi-period bid generation problem with consideration of delivery lead time

Multi-objective evolutionary algorithms (MOEAs) are usually fast to find Pareto fronts in a single run. So, in this section we utilize them to solve our bi-objective bid generation problem. Among MOEAs, NSGA-II due to its efficiency, its ability to solve similar problems, and its ease of use is chosen. Moreover, as there is no benchmark existing in the literature to verify the results obtained by NSGA-II, another GA-based MOEA called NRGA is used as well [START_REF] Hamid | Bi-objective optimization of a multi-product multi-period three-echelon supply chain problem under uncertain environments: Nsga-ii and nrga[END_REF]. In this section we first describe bi-objective decision problems.

A single objective optimization algorithms aim at obtaining an optimal or near optimal solution. For bi-objective optimization problems, decision makers are not satisfied with only one solution returned, because they want to make different compromises among multiple objectives by finding a set of non-dominated solutions. In the following, we first provide some basic definitions about a multi-objective minimization problem with n decision variables and m objectives (m > 1)

[94]:

Minimize y = f (x) = ( f 1 (x), f 2 (x), ..., f m (x))
where x ∈ R n and x ∈ R m .

Definition 1.

A solution b is dominated by another solution a if and only if:

(1) Different techniques are developed to solve multi-objective optimization problems. These algorithms can be classified into meta-heuristic, decision-aided, interactive, fuzzy and scalar ones [START_REF] Chiandussi | Comparison of multi-objective optimization methodologies for engineering applications[END_REF]. For a detailed description of the multi-objective optimization, readers may refer to [START_REF] Collette | Multiobjective optimization: principles and case studies[END_REF]. In the following, two popular metaheuristic algorithms, NSGA-II (Non-dominated Sorting Genetic Algorithm-II based on sorting the population by non-dominance) and NRGA (Non-dominated Ranked Genetic Algorithm) to solve multi-objective optimization problems are utilized. Before presenting the two algorithms, some important concepts of multi-objective optimization are introduced.

f i (a) ≤ f i (b) ∀i ∈ {1, 2, ....., m} (2) f i (a) < f i (b) ∃i ∈ {1,

Non-dominated sorting and crowding distance

To sort a population with size N according to non-domination, each solution must be compared with every other solution in the population to check if it is dominated. At this step, all individuals in the first non-dominated level are obtained. In order to determine the individuals of the next level, the solutions of the first level are deduced and the procedure to sort and compose the non-dominated level is executed again. This method is repeated to find a successive front [70].

Diversity mechanism

In addition to the convergence to the Pareto-optimal set, a good multi-objective optimization algorithm should be able to obtain solutions that maintain a good diversity. In [67], the concept of cuboid is used to measure diversity in the population. A cuboid is a rectangular centered on an individual (a solution) in the front. Figure 5.1 illustrates such a cuboid for a bi-objective problem, To get an estimation of the density of solutions surrounding a particular solution, i, in the population, we calculate the average distance of two points on either side of this point, i, along each of the objectives. This quantity i distance serves as an estimate of the perimeter of the cuboid formed by using the nearest neighbors as the vertices (call this 'crowding distance') [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: Nsga-ii[END_REF].

Furthermore, the total crowding distance value is calculated as the sum of individual distances value corresponding to each objective. In Fig. 5.2, the computation procedure of crowding distance of all solutions in a non-dominated set L is depicted [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: Nsga-ii[END_REF]. In that figure ,L According to Fig. 5.3, the crowding distance for individual X 1 is larger than X 2 , hence, individual X 1 has more probability to be chosen as a parent.

NSGA-II (Non-dominated Sorting Genetic Algorithm-II) implementation

The Non-dominated Sorting Genetic Algorithm is a Multi Objective Optimization (MOO) algorithm and is an instance of an Evolutionary Algorithm from the field of Evolutionary Computation.

NSGA-II is an extension of the Genetic Algorithm for multi objective function optimization. Actually, one of the well-known multi-objective optimization algorithms is NSGA-II, which has three special features. The significant features of NSGA-II are fast non-dominated sorting, fast crowded distance evaluation and simple crowding comparison [START_REF] Yusoff | Overview of nsga-ii for optimizing machining process parameters[END_REF]. Different test problems from previous studies applying NSGA-II are compared in [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: Nsga-ii[END_REF], which claims that this approach outperforms some algorithms like PAES and SPEA in obtaining a more diverse set of solutions [START_REF] Shyam | Multi-objective optimization of surface grinding process using nsga ii[END_REF]. Overall, NSGA-II can be summarized by the following steps [START_REF] Yusoff | Overview of nsga-ii for optimizing machining process parameters[END_REF]:

Step 1: Initialize the population Initialize the population using a solution generation procedure. For the bi-objective problem studied, we apply the initial solution procedure in Chapter 4 to initialize the population. The considered problem in this chapter is multi-period bid generation problem with delivery lead time. The chromosome structure is the same as chromosome structure in Chapter 4, which is composed of three vectors, X , Y , and Z indicating pickup and delivery nodes, period allocation for each request and assigning a vehicle to each request.

Step 2: Non dominated sort Sort the population based on non-domination.

Step 3: Calculation of crowding distances After sorting the population, the crowding distance value is calculated as the sum of individual distance values corresponding to each objective.

Step 4: Selection

The individuals are chosen based on the rank of their front in the sorting and on the crowding distance. The selection of individuals is performed by tournament selection approach with crowding comparison operator.

Step 5: Genetic Operations Offspring generated by the operators previously described for the GASA algorithm. The crossover operator over vector X is single point crossover and the crossover operator over vector Y and Z are uniform crossover which both of them are described in Chapter 4. The mutation operators over the three vectors are also introduced in Chapter 4.

Step 6: Combination and selection

The population of offspring and current generation are combined and the individuals of the next generation are determined by selection. The new generation is composed by each front subsequently until the population size exceeds the current population size [START_REF] Yusoff | Overview of nsga-ii for optimizing machining process parameters[END_REF].

Step 7: Stop criterion

The algorithm stops when a prespecified maximum number of iterations is reached.

NRGA (Non-dominated Ranked Genetic Algorithm) implementation

NRGA is also a multi-objective genetic algorithm to find Pareto optimal solutions. NRGA is similar to NSGA-II with a difference wherein the selection operation a roulette wheel strategy is employed [72]. In NRGA, a fitness value representing rank is assigned to each individual of the population. In this regard, two ranked based roulette wheel selection strategies including: (I) select the fronts and (II) choose solutions from the fronts, are used [72], [START_REF] Al | Non-dominated ranked genetic algorithm for solving constrained multi-objective optimization problems[END_REF], [START_REF] Habib | Developing two multi-objective evolutionary algorithms for the multi-objective flexible job shop scheduling problem[END_REF], [START_REF] Al Jadaan | Non-dominated ranked genetic algorithm for solving multi-objective optimization problems: Nrga[END_REF].

P f = 2 × rank f (NF) × ((NF) + 1) f = 1, .., NF (5.20)
P f s = 2 × rank f s (NS) f × ((NS) f + 1) f = 1, .., NF, s = 1, ..., NS (5.21)
In the equations (5.20) and (5.21), NF and (NS) f are the number of fronts and the number of solutions in front f , respectively. Based on equation (5.20), a front with highest rank has the highest probability to be selected. According to equation (5.21), solutions with more crowding distance have higher selection probability. The roulette wheel selection is applied until a desired number of solutions is reached. The algorithm stops when a predetermined number of iterations is obtained. Hence, our preference is the solution located in the higher front rank. If both solutions are embedded in the same front, the solution with a higher crowding rank distance is preferred

[70].

Computational study

To assess the performance of GASA, ITS, NSGA-II, and NRGA algorithms, we use the instances in [65], which their explanations are in Chapter 4. We executed all algorithms on the instances.

The characteristics of the instances include the number of requests, the demand of each request, time windows of pickup and delivery nodes, the number of vehicles, and the capacity of each vehicle have been explained in Chapter 4. To include the period concept in the instances, we assume the number of periods is 5 and each day has predetermined reserved requests. The results unveil that both GASA and ITS algorithm for the single-objective bid generation problem studied remarkably outperform CPLEX, while the GASA algorithm outperforms the ITS algorithm. To compare two bi-objective algorithms, NSGA-II and NRGA, we use different metrics as defined in the next subsection.

Comparison Metrics for Multi-Objective Optimization Algorithms

In order to analyze the performance of each algorithm, two criteria must be evaluated: Efficiency and effectiveness. In the evaluation of a single objective algorithm, the value of the objective function corresponds to the effectiveness and the computation time represents the efficiency of the algorithm. We solved the mathematical programming model of our problem by CPLEX 12.6 called in C++ with Visual studio 12 on a laptop with an Intel core i5 CPU and 4.00 GB RAM.

Note that for the instances with 30 requests and the instances more than 30 requests, it is impossible to solve the model optimally by CPLEX after 2 hours and 3 hours of running, respectively.

However, to evaluate the efficiency and effectiveness of a multi-objective algorithm, there are different metrics explained below. These metrics can be used to get a comprehensive picture of the algorithm's ability [START_REF] Daniel | Enabling carrier collaboration via order sharing double auction: a singapore urban logistics perspective[END_REF]. Overall, for a multi-objective optimization algorithm, the diversity of Pareto solutions found and also its convergence are two important factors [START_REF] Deb | Multi-Objective Optimization Using Evolutionary Algorithms[END_REF]. Computational time can still be applied as a suitable metric to evaluate the efficiency of an algorithm.

Diversification metric (D or diversity).

The diversification metric measures the spread of the solutions found and is defined in [START_REF] Zitzler | Evolutionary algorithms for multiobjective optimization: Methods and applications[END_REF].

In Fig. 5.4, diversity metric is illustrated.

Spacing metric (S)

The standard deviation of the solutions distances in the Pareto front is defined as the spacing metric. In Fig. 5.4, the spacing metric is illustrated where |n| [START_REF] Hajipour | Bi-objective vibration damping optimization for congested location-pricing problem[END_REF].

d i = min k∈n,k =i { M m=1 | f i m -f k m |}, f (i) m

The number of Pareto solutions (NOS)

This metric enumerates the number of Pareto solutions in the optimal front.

Mean Ideal distance (MID).

This metric measures the proximity of solutions from the ideal point that is (0, 0) on the Pareto front appraisal [START_REF] Habib | Developing two multi-objective evolutionary algorithms for the multi-objective flexible job shop scheduling problem[END_REF]. In the following equation (5.22), f ji is the value of objective function in the i th solution of optimal front.

M ID = 1 NOS NOS i=1 C i where C i = 2 j=1 f 2 ji (5.22) Time.
Time is an important criterion in comparing two algorithms.

Whereas in terms of diversity and NOS metrics, larger values are desirable, for the spacing metric, MID, and CPU time, smaller values are desired [START_REF] Hajipour | Bi-objective vibration damping optimization for congested location-pricing problem[END_REF].

Algorithm parameter tuning

To apply the taguchi approach to parameter calibration of a bi-objective optimization algorithm, criteria for comparing two solutions must be chosen [START_REF] Hamid | A multi-objective facility location model with batch arrivals: two parameter-tuned metaheuristic algorithms[END_REF]. Two important criteria are 1) convergence and 2) diversity of Pareto solutions. As we mentioned previously, there are different metrics TIME WINDOWS, PROFITS, RESERVED REQUESTS, AND DELIVERY LEAD TIME for comparing multi-objective optimization algorithms. Among them, computational time and mean ideal distance (MID) are two metrics for evaluating the convergence of the algorithms while other metrics are applied for evaluating the diversity of the Pareto solutions. In the suggested metrics, diversity and MID are integrated through the following equation (5.23). The two criteria are considered at the same time. Accordingly, by applying this integrated metric as the response of the Taguchi approach, a combination of main signals can be proposed. So, we can gain precise outputs. This metric is called the multi-objective coefficient of variation (MOCV) [START_REF] Hajipour | Bi-objective vibration damping optimization for congested location-pricing problem[END_REF], [START_REF] Hamid | A multi-objective facility location model with batch arrivals: two parameter-tuned metaheuristic algorithms[END_REF]:

M OCV = M ID D iversit y (5.23)
When applying Taguchi method, the level of each factor taken is reported in Table 5.3. For GASA and ITS algorithms, we use the same parameters which have been determined in Chapter 3.

By numerical experiments using Taguchi method, we find that the predetermined values of all parameters in Chapter 3 are appropriate. For each algorithm, three levels (i.e. low, medium and high) are defined for each factor. By using Minitab Software, L9 design is exploited for NSGA-II and NRGA. The orthogonal arrays of these designs and the gained responses are illustrated in Table 5.4 and Table 5.5 for NSGA-II and NRGA respectively. For each algorithm, the effect plots for S/N ratio are presented in Fig. 5.5 and Fig. 5.6. By using these results for each algorithm, the appropriate values of all parameters are set and reported in Table 5.6.

Results and Analysis

RPD is one of the well-developed approaches for measuring the efficiency of an algorithm with respect to another algorithm. In Chapter 3, we described completely RPD indicator in equation (3.25). In this subsection, we apply it to compare algorithms. Table 5.7 illustrates the results of GASA and ITS over the instances of Chapter 4 while Table 5.8 shows their results in terms of RPD. Their statistical analysis is given in Table 5.9. The results of NRGA and NSGA-II in each metric are indicated in Table 5.10 and Table 5.11. We calculate the RPD of each metric after three execution of each algorithm. Two gaps, Gap ITS and Gap G AS A , are defined in Table 4.9. All gaps defined in Table 5.7 are in percentage (%). In order to show the significant difference in terms of RPD (metrics for bi-objective problems algorithms), the algorithms are statistically analyzed according to obtained solutions via analysis of variance (ANOVA) tests [START_REF] Hajipour | Bi-objective vibration damping optimization for congested location-pricing problem[END_REF]. The procedure of ANOVA including F-test value and also P-value on RPD (each metric for bi-objective algorithms) are summarized in Table 5.9 and Table 5.12. The results are analyzed at 95% confidence level. Therefore, for the single objective problem, there are significant differences and the average results of RPD for GASA is better than ITS. Additionally, the computation time of GASA is shorter than ITS according to Table 5.7. According to Table 5.7, for some instances when the number of requests are 20, CPLEX could not obtain a solution in a preset running time while ITS and GASA have obtained a solution. Indeed, for all instances with the number of requests 20, no feasible solution is obtained by CPLEX in the time limitation 1 hour, so we compare the solutions obtained by our algorithms based on their relative gaps with the upper bound obtained by CPLEX, i.e., using the above-mentioned criteria. Our algorithms can find an optimal solution for all 20 requests instances and can find a solution with the relative profit gap smaller than 5.92%. For medium 30 requests instances, our GASA algorithm can find a solution with the gap smaller than 6.2%, whereas our ITS algorithm can find a solution with the gap smaller than 7.96%. For 40 requests instances, our GASA algorithm can find a solution with the gap smaller than 9.69%, whereas our ITS algorithm can find a solution with the gap smaller than 11.72%. For large 50 requests instances, our GASA algorithm can find a solution with the gap smaller than 11.69%, whereas our ITS algorithm can find a solution with the gap smaller than 12.54%. For 100 requests instances, our GASA algorithm can find a solution with the gap smaller than 16.84%, whereas our ITS algorithm can find a solution with the gap smaller than 18.77%.

For the bi-objective problem, in terms of MID, Time, and NOS, there are significant differences between the two algorithms, whereas in MID metric, NSGA-II is better than NRGA, NRGA outperforms NSGA-II in NOS and time. It means that NSGA-II has a better convergence performance in MID, whereas in diversity metric, NRGA performs better. In the other metrics, TIME WINDOWS, PROFITS, RESERVED REQUESTS, AND DELIVERY LEAD TIME there are not significant differences between the two algorithms and the average results of the metrics indicates which algorithm outperforms another one. The average in the spacing and diversity metrics show NRGA operates better than NSGA-II. Finally, the results of NSGA-II and NRGA for each metric given in Fig. 5.6, Fig. 5.7, Fig. 5.8 and Fig. 5.9, which can confirm the statistical results.

Conclusion

In this chapter, we have presented two methods to evaluate each bid submitted by carriers to the auctioneer. One is evaluating a bid according to a score function which is defined as cost plus weighted delivery lead time as in a multi-attribute score auction. The other is evaluating a bid according to its multi-attributes. Accordingly, each carrier has two ways to determine its bid, one Numerical experimental results show that our algorithms give promising results compared with commercial solver CPLEX. Besides, the ALNS algorithm outperforms the two other algorithms not only in finding better solutions but also its running time is better than others.

In Chapter 4, a multi-period Bid Generation Problem (BGP) for a carrier has been considered.

In the problem, there are two different types of requests, reserved requests of the carrier and selective requests. Each request has a pickup and delivery request with two time windows. For each selective request there is a period window while each reserved request has a predetermined period to be served. A period window specifies the earliest period and the latest period the request must be served while a time window shows the earliest and latest service time and is allocated to both pickup point and the delivery point. In addition, each selective request is associated with a profit that is the price for serving the request provided by a shipper. A hybrid approach that combines a genetic algorithm and simulated annealing (GASA) has been proposed to solve the problem. For the purpose of comparison, we utilized Biogeography-Based Optimization algorithm (BBO) that is a population-based algorithm whose specifications are close to the GA.

The numerical results demonstrated that in spite of CPLEX, the proposed algorithms can find a good feasible solution in a reasonable computation time for large instances.

In the companies, besides minimizing all costs, a shipper interested in reducing the delivery lead time. Reducing delivery lead time has two benefits. At first, shorter delivery lead time makes agile supply chain management and responding to the orders is executed faster. Thus, it improves the ability of shippers to compete in the industry. Second benefit of shorter delivery lead time is choosing the carriers according to the geographic factors. It means that shippers distribute freight volumes to a carrier geographically. Totally, by considering the short delivery lead time, the auctioneer gets involve also in other attributes not only costs. In many acquisition situations although cost is an important attribute to evaluate the orders, carriers care about the quality specifications when estimate the submitted orders by suppliers. To these points, in Chapter 5, we addressed delivery lead time in transportation service procurement, which is conducted by shippers and using auctions to purchase transportation service from carriers in the planning stage. Many shippers get involve with delivery lead time in practice; the transportation service is better when delivery lead time decreases. consequently, we considered two ways to comprise delivery lead time in the problem. Firstly, a bi-objective problem has been considered, where the first objective is the maximization of all profits while the other is the minimization of delivery lead time. After presenting the mathematical model, we solved it by NSGAII and NRGA and compared them by well-known metrics. Secondly, we assumed in a single objective problem delivery lead time included as an attribute in the objective function by using some multi-criteria decision making (MCDM) methods. GASA and ITS have been employed to solve the model. The results indicated both of them can get a feasible solution in large instances, on the contrary, CPLEX could not.

PERSPECTIVES

In summary, the principal contributions of this thesis is comprised three new concepts appeared in carrier collaboration, presenting mathematical models for them, and the development of efficient solution methods: 1) the centralized multi-carrier PDPTWR, a new vehicle routing problem with multi-carriers to allocate exchangeable requests to the suitable carriers. 2) the multi-period BGP:

A new multi-period vehicle routing problem to identify profitable requests in a period. 3) the multi-period BGP with minimizing delivery lead time, a new bid generation problem appeared in LTL carrier collaboration in order to reduce the delivery lead time and increasing the profits.

Perspectives

Although we have suggested a complete scheme to address the requests re-allocation problem in LTL carrier collaboration, there are still other studies to be done to develop the models, the solution issues, and make them more suitable in the realistic carrier collaboration environments.

Firstly, for the multi-carrier centralized PDPTWR, we have assumed all requests are deterministic while in the realistic environment, requests can be stochastic. Thus, in the future study we can focus on the stochastic requests particularly exchangeable requests can be stochastic.

Secondly, for the multi-period PDPTWPR via BGP, it will be an interesting issue to deal with classified selective requests wherein each period if a selective request in each category cannot be served, serving all selective requests in the same category will not be possible. In the realistic collaboration environment, sometimes, ignoring a group of requests is reasonable to save costs.

Thirdly, we can add the effect of decreasing CO2 emission to our model in the third problem.

Although reducing the delivery lead time is important to meet the customer's satisfaction, CO2 emission and increasing greenhouse gases in the environment is a critical issue in the last years as it has become the huge problem in the world and most of the well-developed countries make plans to reduce the effects of CO2 emissions in the atmosphere. Consequently, in our model minimization of CO2 emission could be included to take into account the environmental aspect besides cost and profit.

Finally, profit allocation approaches have not addressed in this thesis while this subject is necessary for collaborative logistics implementing. In the literature, the requests re-allocation problem and the profit allocation problem are often manipulated independently. It would be better if the two problems could be examined together, so better results can be achieved compared to observed them separately. Dans cette thèse, nous nous concentrons sur le premier problème qui est également considéré comme un problème de planification collaborative des transports (CTP) [START_REF] Wang | Collaborative transportation planning of less-than-truckload freight[END_REF], [START_REF] Wang | Operational transportation planning of freight forwarding companies in horizontal coalitions[END_REF], [START_REF] Wang | A rolling horizon auction mechanism and virtual pricing of shipping capacity for urban consolidation centers[END_REF]

x i jkm = 0 ∀i ∈ W, ∀k ∈ K m , ∀m ∈ M (A.1) m∈M j∈V ; j =i k∈K m x i jkm = 1 ∀i ∈ W (A.2) j∈P; j =i x i jkm ≤ 1 ∀k ∈ K m , ∀i = m ∈ M (A.3) x i jkm ∈ {0, 1} ∀i, j ∈ V , ∀k ∈ K m , ∀m ∈ M (A.19) y ikm ∈ {0, 1} ∀i ∈ R, ∀k ∈ K m , ∀m ∈ M (A.20) U ikm ≥ 0 ∀i ∈ V , ∀k ∈ K m , ∀m ∈ M (A.21) L ikm ≥ 0 ∀i ∈ V , ∀k ∈ K m , ∀m ∈ M (A.
, où R = ( l∈H R l r ) R s . R l
r est l'ensemble des demandes réservées qui doivent être traitées dans la période l et R s l'ensemble des demandes sélectionnées. Chaque demandes sélective a une fenêtre de période de service et deux fenêtres de temps: La fenêtre de période de service détermine les périodes auxquelles la demande sélective peut être exécutée et les deux fenêtres de temps déterminent à quels moments de chaque période le noeud de ramassage et le noeud de livraison de la demande peuvent être visités par un véhicule qui sert la demande. Les demandes sélectives et réservées sont associées à deux fenêtres de temps alors que seules les demandes sélectives sont associées à une fenêtre de période de service (la période pendant laquelle chaque demandes réservée doit être servie est prédéfinie). La fenêtre temporelle du noeud de ramassage i et du noeud de livraison i + n de la demandes i sont indiqués respectivement par [e i , l i ] et [e i+n , l i+n ]. La fenêtre de période de service pour chaque demandes sélective i est représentée par [E i , L i ]. Chaque demande réservée i ∈ R l r doit être servie dans sa période prédéfinie l, l ∈ H. Le temps de déplacement et le coût de transport entre deux noeuds i et j sont supposés être les mêmes et sont indiqués par t i j et c i j , respectivement. La durée maximale de chaque itinéraire i est limitée par T. Le problème de la génération d'offres sur plusieurs périodes peut être formulé sous la forme d'un modèle de programmation linéaire à entiers mixtes. Dans le modèle, les paramètres BM i j = l j -e i sont utilisés pour formuler linéairement les contraintes de fenêtre de temps tandis que C i = Q + d i est utilisé en contraintes de capacité. Les variables de décision du modèle comprennent les variables binaires, x i jkh et y ikh et les variables réelles U ikh et CV ikh définies comme suit: Ecole Doctorale "Sciences pour l'Ingénieur" Thèse réalisée en partenariat entre :

x i jkh =         

  test problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 5.8 Graphical comparisons of MID metric for NSGA-II and NRGA algorithms on all test problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 xv LIST OF FIGURES 5.9 Graphical comparisons of Time metric for NSGA-II and NRGA algorithms on all test problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.10 Graphical comparisons of Spacing metric for NSGA-II and NRGA algorithms on all test problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.11 Graphical comparisons of NOS metric for NSGA-II and NRGA algorithms on all test problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . , companies compete with each other to satisfy customers' increasing expectations and they have to reduce costs and improve profitability to survive in business world.

Figure 3 . 1 :

 31 Figure 3.1: Illustration of chromosome's structure.

Figure 3 . 2 :

 32 Figure 3.2: The single point crossover on two X vectors.

Figure 3 . 3 :

 33 Figure 3.3: The crossover on two Z vectors.

Figure 3 . 4 :

 34 Figure 3.4: The mutation operator over vector Z.

3. 4

 4 . NUMERICAL EXPERIMENTS model of our problem by CPLEX 12.6 called in C++ with Visual studio 12 on a laptop with an Intel core i5 CPU and 4.00 GB RAM. Note that for the medium size instances with 30 requests for each carrier and 4 vehicles and large size instances with 50 requests per carrier and 8 vehicles, it is impossible to solve the model optimally by CPLEX after 2 hours and 3 hours of running, respectively.

Figure 3 . 5 :

 35 Figure 3.5: Outputs of Taguchi ratio for ITS.

Figure 3 . 6 :

 36 Figure 3.6: Outputs of Taguchi ratio for GASA.

Figure 3 . 7 :

 37 Figure 3.7: Outputs of Taguchi ratio for ALNS (3 × 5, 3 × 8).

Figure 3 . 8 :

 38 Figure 3.8: Outputs of Taguchi ratio for ALNS (3 × 15).

Figure 3 . 9 :

 39 Figure 3.9: Outputs of Taguchi ratio for ALNS (3 × 30).

Figure 3 . 10 :

 310 Figure 3.10: Outputs of Taguchi ratio for ALNS (3 × 50).

4. 1 .

 1 LITERATURE REVIEW exact bidding strategy is based on the concept of elementary request combinations. The author

  with profit is in[74]. In the paper, asymmetric prize collecting traveling salesman problem has been demonstrated. The objective of the problem is to minimize the cost of the routes and the penalty value of unserved customers.The pickup and delivery problem with multi-vehicles and profit is suggested in[35]. In the article, there are multi-carriers and the customers with high profits are served. To solve the problem, general variable neighborhood search (GVNS) is compared with guided local search (GLS).

Figure 4 . 1 :

 41 Figure 4.1: Illustration of chromosome's structurer

Figure 4 . 2 :

 42 Figure 4.2: Model of immigration λ and emigration µ probabilities [90].

Figure 4 . 3 :

 43 Figure 4.3: Output of Taguchi ration for BBO.

Figure 4 . 4 :

 44 Figure 4.4: Output of Taguchi ration for GASA.

Figure 4 . 5 :

 45 Figure 4.5: Output of comparing GASA and BBO with RPD indicator.

  this chapter, a new vehicle routing problem appeared in carrier collaboration via a combinatorial auction (CA) is studied. A carrier with reserved requests wants to determine within a time horizon of multi-periods (days) which pickup and delivery requests to serve among the requests open for bid of the auction to maximize its own profit subject to vehicle capacity, time windows constraints, and the maximum duration of each route. It is a multi-Periods Pickup and Delivery Problem with Time Windows, Profits, and both Reserved and Selective Requests.

  WITH PICKUP AND DELIVERY, TIME WINDOWS, PROFITS, RESERVED REQUESTS, AND DELIVERY LEAD TIME M anagement in the transport sector occurs along traditional lines rather than following a contemporary integrated approach [69]. Many manufacturers are seeking optimized logistics solutions to reduce transportation costs. Optimized logistics solutions that improve the transportation planning by one percent would save millions of euros. Taking the multi-billion transportation market into account, innovative ideas, and effective logistics solutions

( 5 . 8 )

 58 -(5.11) specify time windows constraints on the pickup and delivery nodes of each request and the constraint on the maximum duration of each route. Constraints (5.12) and (5.13) check vehicle capacity. Equations (5.14)-(5.17) define all variables. To linearize the last term of the objective function, two constraints (5.18) and (5.19) are added.

Figure 5 . 1 :

 51 Figure 5.1: Cuboid along locally non-dominated frontier [70].

  [i] .m addresses the value of m th objective function of the i th individual in the set L [70].

Figure 5 . 2 :

 52 Figure 5.2: The crowding distance computation procedure of all solutions in a non-dominated set [70].

Figure 5 . 3 :

 53 Figure 5.3: Crowding distance for individuals X 1 and X 2 [70].

Figure 5 . 4 :

 54 Figure 5.4: The spacing and diversity metrics in bi-objective problems [70].

Figure 5 . 5 :

 55 Figure 5.5: Outputs of Taguchi ratio for NSGA-II.

Figure 5 . 6 :Table 5 . 6 :

 5656 Figure 5.6: Outputs of Taguchi ratio for NRGA.

Figure 5 . 7 :

 57 Figure 5.7: Graphical comparisons of Diversity metric for NSGA-II and NRGA algorithms on all test problems. 98

Figure 5 . 8 :

 58 Figure 5.8: Graphical comparisons of MID metric for NSGA-II and NRGA algorithms on all test problems.

Figure 5 . 9 :

 59 Figure 5.9: Graphical comparisons of Time metric for NSGA-II and NRGA algorithms on all test problems.

Figure 5 . 10 :

 510 Figure 5.10: Graphical comparisons of Spacing metric for NSGA-II and NRGA algorithms on all test problems.

Figure 5 . 11 :

 511 Figure 5.11: Graphical comparisons of NOS metric for NSGA-II and NRGA algorithms on all test problems.

  is minimizing a score (cost and delivery lead time) and the other is minimizing both attributes of a bid (cost plus weighted delivery lead time). At first, we focused on the first way by assuming a score function composed of cost and weighted delivery lead time and formulate the multi-period bid generation problem as a single objective mathematical model. After presenting the MILP model for the problem, we solved it by two metaheuristic algorithms GASA and ITS. Then, we have taken the second way by evaluating a bid according to two attributes. We have presented a bi-objective mathematical model for multi-period BGP. To solve the bi-objective problem, NSGA-II and NRGA have been applied. They are compared according to well-known metrics and the superiority of each algorithm in each metric has been determined. About the single objective problem, GASA outperforms the other algorithm in terms of profit and computation time. For the bi-objective problem, in MID, Time, and NOS there are significant differences between two algorithms, NSGA-II and NRGA, whereas in MID metric, NSGA-II is better than NRGA, NRGA algorithm overcomes NSGA-II in NOS and time. It means that NSGA-II has a better convergence performance in MID, whereas in diversity features, NRGA performs better. In the other metrics, there are not significant differences and the average results in the metrics indicate which outperforms another one. The average in the spacing and diversity metrics show NRGA performs better than NSGA-II. , collaborative logistics and especially carrier collaborative transportation have been appeared as a beneficial technique for small to medium-sized freight carriers to ameliorate profitability by diminishing empty back-hauls by vehicle reposition and improving vehicle fill rates. In this thesis, we discussed collaborative transportation planning (CTP) raised in carrier collaboration, particularly the carrier collaboration in less than-truckload (LTL) transportation.Two key-subjects are often discussed for carrier collaboration in LTL transportation: The request re-assignment problem and the post-collaboration profit allocation problem. In this thesis, we concentrated on the requests re-assignment problem in centralized multi-carrier collaboration and suggested an auction-based carrier collaboration approach for CTP with profits. In this field, three main sub-problems have been considered: Multi-carrier centralized CTP with pickup and delivery requests with time windows and reserved requests, periodic bid generation problem (BGP) and periodic bid generation problem (BGP) with delivery lead time.After studying the research background in Chapter 1 and reviewing the collaborative transportation planning state-of-the-art in Chapter 2, we suggested in Chapter 3, a multi-carrier centralized CTP with pickup and delivery requests and time windows with reserved requests (PDPTWR), a new vehicle routing problem developed in LTL carrier collaboration.The multi-carrier centralized PDPTWR involves exchangeable requests, which can be exchanged among carriers in a coalition, while each carrier keeps reserved requests to serve by the carrier itself. After presenting mathematical programming model, three metaheuristic algorithms have been developed as solution methods: An adaptive large neighborhood search (ALNS), a CHAPTER 6. CONCLUSIONS AND PERSPECTIVES hybrid Genetic Algorithm and Simulated Annealing (GASA) and an improved tabu search (ITS).

  les petites et moyennes entreprises (PME) est cruciale pour améliorer leur situation économique. En effet, cette collaboration au sein d'un réseau est une approche importante pour réaliser des bénéfices dans un environnement très concurrentiel.Le partage des demandes entre les transporteurs génère des profits pour toutes les entreprises, et assure la satisfaction des demandes des clients. Les raisons qui motivent les industriels et les chercheurs à mettre en oeuvre la planification de la collaboration entre transporteurs sont la concurrence féroce sur les marchés mondiaux, la courte durée de vie des produits, l'augmentation du coût du carburant, le prix de la main-d'oeuvre et l'effet de toutes ces raisons sur les profits des entreprises[START_REF] Cruijssen | Horizontal cooperation in logistics: Opportunities and impediments[END_REF]. Par conséquent, la collaboration entre les transporteurs est une stratégie pertinente pour les chercheurs et les praticiens de l'industrie afin de réduire les retours à vide des véhicules et d'augmenter leurs taux de remplissage[START_REF] Chen | Mathematical model and solution approach for collaborative logistics in less than truckload (LTL) transportation[END_REF].Une coalition entre plusieurs acteurs du même niveau d'opérations logistiques est définie comme une collaboration de transporteur. Grâce à cette collaboration, de nombreux transporteurs peuvent échanger leurs demandes de transport entre eux pour arriver à une meilleure complémentarité entre les demandes. Cet échange de demandes peut améliorer la planification de tournées des véhicules tout en réduisant les retours à vide et, par conséquent, en augmentant leurs profits de transport. Deux problèmes importants sont discutés dans le problème lié à la collaboration. Le premier est de savoir comment ré-attribuer de façon optimale les demandes de transport entre transporteurs pour maximiser le profit total. Le second est de définir comment répartir les bénéfices obtenus après une collaboration équitable entre les transporteurs au sein d'une coalition, afin d'assurer la pérennité de cette alliance[65].

1A. 4 . 1 A. 5 ConclusionA. 6 Perspectives

 4156 Si et seulement si dans la période h, le véhicule k visite directement le noeud j après le noeud i.0Dans le cas contraire.A.4. PROBLÈME DE GÉNÉRATION D'ENCHÈRES SUR PLUSIEURS PÉRIODES AVEC PRISE EN COMPTE DES DÉLAIS DE LIVRAISONaméliore la capacité des expéditeurs à être concurrentiels dans l'industrie. Deuxièmement, l'avantage d'un délai de livraison plus court réside dans le choix des transporteurs en fonction des facteurs géographiques. Cela signifie que les expéditeurs distribuent les volumes de fret à un transporteur géographiquement[START_REF] Hu | Transportation service procurement problem with transit time[END_REF]. En fait, en considérant le délai de livraison court, le commissaire-priseur s'implique aussi dans d'autres attributs non seulement économiques.Dans de nombreuses situations d'acquisition, bien que le coût soit un attribut important dans l'évaluation des commandes, les transporteurs se soucient des spécifications de qualité lorsqu'ils estiment les commandes soumises par les fournisseurs[START_REF] Ghosh | Scoring auctions: A brief survey[END_REF].Compte tenu de l'importance du délaide livraison dans BGP, de son application dans les problèmes réels de transport et du fait que cette question n'a pas encore été abordée dans la littérature, nous nous concentrons sur ce sujet dans la présent section. En effet, dans ce dernier, nous avons envisagé l'enchère combinatoire pour la collaboration entre transporteur, chaque transporteur détermine les demandes (échangeables) de soumission (les demandes échangeables à sélectionner) en résolvant un BGP. Après avoir reçu les offres de tous les transporteurs, le commissaire-priseur (une plate-forme d'enchères) détermine les transporteurs gagnants et leurs offres gagnantes. Concernant le commissaire-priseur, il a deux façons d'évaluer chaque offre des transporteurs. L'une consiste à évaluer une offre en fonction de la notation qui est définie comme le coût et le délai de livraison, comme dans l'enchère de notation multi-attributs. L'autre façon d'évaluer une offre est en fonction de ses multiples attributs (dans notre cas, un attribut est le coût, l'autre attribut est le délai de livraison). Par conséquent, chaque transporteur a également deux façons de présenter son offre, l'une consiste à présenter une note (coût et délai de livraison) et l'autre à présenter les deux attributs d'une offre (coût et délai de livraison). Par conséquent, dans la présent section, nous examinons les deux points de vue sur le problème du transport collaboratif. La première approche est une méthode des objectifs pondérés, c'est-à-dire que nous attribuons un poids à chaque objectif et transformons ensuite deux objectifs en un seul objectif pondéré. L'autre méthode est une méthode bi-objective qui est traitée avec des fonctions objectives séparées sans les transformer en une seule fonction objective. Par conséquent, deux méthodes de traitement avec les deux objectifs supposés conduisent à deux problèmes: le BGP multi-période à objectif unique avec délai de livraison et le BGP multi-période bi-objectif avec délai de livraison. Description et modèle mathématique Le problème considéré dans ce section est un problème de planification du transport avec les demandes de ramassage et de livraison, les fenêtres de de temps et de période sur un graphique dirigé G = (V , E), où V est l'ensemble des noeuds et E est l'ensemble des arcs, avec les spécifications suivantes: Chaque demande i a deux points, un point de ramassage i et un point de livraison n + i, où n représente le nombre de demandes. Aussi, la demande du point de ramassage est égale à la demande du point de livraison. Le noeud de livraison de chaque demande à ce problème comme le cas où la quantité de ramassage/livraison est inférieure à la capacité du véhicule et tous les véhicules sont homogènes. Le coût de la satisfaction de la demande des clients dépend de la distance totale parcourue par les véhicules. Chaque demande sélective a une fenêtre de période de service et deux fenêtres de temps. La fenêtre de période de service définit les périodes pendant lesquelles chaque demande sélective peut être traitée et les deux fenêtres de temps déterminent à quels moments de chaque période le noeud de ramassage et le noeud de livraison de la demande peuvent être visités par un véhicule qui dessert cette demande, par exemple les fenêtres matin et après-midi séparées par une pause déjeuner. Les demandes sélectives et réservées sont associées à deux fenêtres de temps, alors que seules les demandes sélectives sont associées à une fenêtre de période de service (la période pendant laquelle chaque demandes réservée doit être servie est prédéfinie). Si une demande sélective est servie, la période la plus appropriée pour la servir devrait être déterminée. Le problème de la génération d'offres sur plusieurs périodes peut être formulé sous la forme d'un modèle de programmation linéaire à entiers mixtes. Le but du problème est de répondre à toutes les demandes réservées dans leur période prédéfinie et de déterminer quelles demandes sélectives doivent être traitées pour augmenter le bénéfice total. Les paramètres du problème sont énumérés dans le Tableau A.3, tandis que les variables de décision utilisées sont présentées dans le Tableau A.4. max ( i∈R h∈H k∈K p i y ikh -h∈H i∈V j∈V k∈K c i j x i jkm -j∈R s α j ( h∈[E i ,L i ] k∈K y jkh )) sujet à:j∈V ; j =i x jikh -j∈V ; j =i x i jk = 0 ∀i ∈ W, ∀k ∈ K, ∀h ∈ H (A.40) k∈K j∈P; j =0 h∈H x 0 jkh ≥ 1 (A.41) k∈K i∈D;i =(2n+1) h∈H x i(2n+1)kh ≥ 1 (A.42) k∈K y ikh = 1 ∀h ∈ H, ∀i ∈ R r l (A.43) h∈[E i ,L i ] k∈K y ikh ≤ 1 ∀i ∈ R s (A.44) j∈V , j =i,0 x j(n+i)kh = y ikh ∀i ∈ P, k ∈ K, ∀h ∈ H (A.45) A.5. CONCLUSION prédéterminée. L'équation (A.44) indique que chaque demande sélective peut être traitée au cours d'une période de sa fenêtre de service ou ne pas l'être. Les contraintes (A.45) et (A.46) garantissent que si une demande est servie dans une période, son noeud de livraison doit être visité après son noeud de ramassage avec le même véhicule dans la même période. Les équations (A.47)-(A.50) précisent les contraintes de fenêtre de temps sur les noeuds de ramassage et de livraison de chaque demande et la contrainte sur la durée maximale de chaque route. Les contraintes (A.51) et (A.52) contrôlent la capacité du véhicule. Les équations (A.53)-(5.56) définissent toutes les variables. Pour linéariser la dernière composante de la fonction objectif, deux contraintes (5.57) et (5.58) sont utilisées. Lorsque les expéditeurs se préoccupent surtout du temps de transit (délai de livraison), un temps de transit plus court permet d'offrir un meilleur service de transport. Il est possible de considérer un problème bi-objectif pour maximiser, d'une part, les profits et minimiser d'autre part le temps de transit et pour évaluer l'effet de la minimisation du délai de livraison sur le profit maximal. Cela signifie que l'une des fonctions objectives est la maximisation du profit et l'autre est la minimisation du délai de livraison. Par conséquent, dans le modèle précédent, le délai de livraison sera considéré comme une deuxième fonction objectif. Première fonction objectif: max ( i∈R h∈H k∈K p i y ikh -h∈H i∈V j∈V k∈K c i j x i jkm ) Deuxième fonction objectif: min j∈R s α j ( h∈[E i ,L i ] k∈K y jkh ) Au cours des dernières années, la logistiques collaborative et surtout le transport collaboratif entre transporteurs sont apparus comme une technique bénéfique pour les petites entreprises et aux transporteurs de fret de taille moyenne afin d'améliorer leur rentabilité en diminuant les trajets de retour à vide par le repositionnement des véhicules et en améliorant leur taux de remplissage. Dans cette thèse, nous nous avons discuté de la planification concertée du transport (CTP) découlant de la collaboration des transporteurs, en particulier de la collaboration des transporteurs dans le transport de chargement partial (LTL). Deux sujets clés sont souvent discutés pour la collaboration des transporteurs dans le transport de chargement partial: le problème de la réaffectation des demandes et le problème de la post-collaboration Ces problèmes influencent grandement les bénéfices du transporteur. Dans cette thèse, nous nous sommes concentrés sur le problème de la réaffectation des demandes dans le cadre d'une collaboration centralisée entre plusieurs transporteurs et nous avons proposé une approche de collaboration entre transporteurs fondée sur les enchères pour le PTP avec profits. Dans ce domaine, trois principaux sous-problèmes sont pris en compte: CTP centralisé multi-opérateurs avec demandes de ramassage et de livraison avec fenêtres de temps et demandes réservées, le problème de génération périodique d'enchères et (BGP) avec délai de livraison dans la collaboration entre opérateurs via un échange combinatoire. Au début, nous avons étudié le contexte de la recherche dans le Chapitre 1 et examiné l'état d'avancement de la recherche sur la planification concertée des transports dans le Chapitre 2. Puis, dans le Chapitre 3, nous nous sommes concentrés sur le CTP centralisé multi-transporteur avec ramassage et livraison avec fenêtres de temps et les demandes réservées (PDPTWR) qui est nouveau défi dans la thématique des tournées de véhicules. Le PDPTWR centralisé multi-transporteur implique des demandes échangeables, qui peuvent être échangées entre les transporteurs au sein d'une coalition, tandis que chaque transporteur conserve les demandes réservées pour lui-même. Après la présentation d'un modèle de programmation mathématique, trois algorithmes métaheuristiques ont été développés comme méthodes de solution: une recherche adaptative de grand voisinage (ALNS), un algorithme génétique hybride et recuit simulé (GASA) et une recherche tabu améliorée (ITS). Les résultats expérimentaux numériques montrent que nos algorithmes donnent des résultats prometteurs par rapport aux solveurs commerciaux CPLEX. De plus, l'algorithme ALNS surpasse les deux autres algorithmes non seulement pour trouver les meilleures solutions mais aussi parce que son temps de calcul est meilleur que les autres. Dans le Chapitre 4, un problème de génération d'offres sur plusieurs périodes (BGP) pour un transporteur a été envisagé. Dans ce problème, il y a deux types de demandes différentes, les demandes réservées du transporteur et les demandes sélectives. Chaque demande a un point de ramassage et de livraison avec deux fenêtres de temps. Une fenêtre de période spécifie l'intervalle dans lequel la demande doit être exécutée, alors qu'une fenêtre temporelle indique l'intervalle horaire affectée au point de ramassage et au point de livraison. De plus, chaque demande sélective est associée à un profit qui est le coût de service de la demande fournie par un expéditeur. Une approche hybride combinant un algorithme génétique et un recuit simulé (GASA) a été proposée pour résoudre ce problème. A des fins de comparaison, nous avons utilisé l'algorithme d'optimisation fondé sur la biogéographie (BBO) qui est un algorithme basé sur la population dont les spécifications sont proches à l'GA. Les résultats numériques ont démontré qu'en utilisant CPLEX, les algorithmes proposés peuvent trouver une bonne solution réalisable dans un temps de calcul raisonnable pour des cas importants. Dans les entreprises, en plus de minimiser tous les coûts, un expéditeur est intéressé par la réduction des délais de livraison. La réduction des délais de livraison présente deux avantages. Dans un premier temps, des délais de livraison plus courts permettent la gestion agile de la chaîne d'approvisionnement et la réponse aux commandes est exécutée plus rapidement. Ainsi, il améliore la capacité des expéditeurs à soutenir la concurrence dans l'industrie. Le deuxième avantage d'un délai de livraison plus court est le choix des transporteurs en fonction des facteurs 126 A.6. PERSPECTIVES géographiques. Cela signifie que les expéditeurs distribuent la marchandise à un transporteur suivant le plan géographique. Finalement, en tenant compte du délai de livraison court, le commissaire-priseur s'implique aussi dans d'autres attributs qui ne sont pas seulement des coûts. Dans de nombreuses situations d'acquisition, bien que le coût soit un facteur important pour évaluer les commandes, les transporteurs se soucient des spécifications de qualité lors de l'estimation de l'offre des commandes passées par les fournisseurs. De ce fait, dans le Chapitre 5, nous avons abordé dans le Chapitre 5 la question du délai de livraison dans le cadre de l'approvisionnement en services de transport, qui est effectué par les expéditeurs au moyen d'enchères pour sélectionner le service de transport auprès des transporteurs à l'étape de la planification. De nombreux expéditeurs utilisent ceci dans leurs tâches de transport quotidiennes dans le monde réel; le service de transport est meilleur lorsque le délai de livraison est plus court. Par conséquent, nous avons envisagé deux façons d'inclure le délai de livraison dans le problème. Premièrement, un problème bi-objectif a été envisagé, où le premier objectif est la maximisation de tous les profits tandis que l'autre est la minimisation du délai de livraison. Après avoir présenté le modèle mathématique, nous l'avons résolu par NSGAII et NRGA et les avons comparés par des métriques bien connues. Deuxièmement, nous avons supposé que le délai d'exécution du problème était inclus comme attribut dans la fonction objectif en utilisant certaines méthodes de prise de décision multicritères (MCDM). De ce fait, GASA et ITS ont été utilisés pour résoudre le modèle. Les résultats indiquent que les deux peuvent obtenir une solution réalisable dans des cas de large taille, au contraire, CPLEX n'a pas pu le faire. En résumé, les principales contributions de cette thèse comprennent trois nouveaux concepts apparus dans la planification de la collaboration entre transporteurs, la présentation de modèles mathématiques pour eux et le développement de méthodes de solution efficaces: 1) le PDPTWR centralisé à transporteurs multiples, un nouveau problème de tournées des véhicules à plusieurs dépôts pour attribuer les demandes d'échange à un transporteur approprié. 2) le PDPTWPR multipériode via BGP: un nouveau problème de routage multi-période des véhicules pour identifier les demandes rentables sur une période. 3) le PDPTWPR multi-période via BGP avec minimisation de délais de livraison. Ce dernier point est un nouveau problème de génération d'offres est apparu dans la collaboration des transporteurs LTL afin de réduire les délais de livraison et d'augmenter les profits. Bien que nous ayons suggéré un plan complet pour résoudre le problème de réattribution des demandes dans le cadre de la collaboration entre transporteurs de lots brisés, il reste encore d'autres études à réaliser pour élaborer les modèles et les solutions aux problèmes et les rendre plus appropriés dans les environnements réalistes de collaboration entre transporteurs. Premièrement, concernant le (Problème de ramassage et de livraison avec plusieurs trans-porteurs, fenêtres de temps, demandes réservées et demandes échangeables) centralisé à transporteurs multiples, nous avons supposé que toutes les demandes sont déterministes alors que dans un environnement réaliste, les demandes peuvent être stochastiques. Ainsi, dans l'étude future, nous pouvons nous concentrer sur les demandes stochastiques, en particulier les demandes échangeables peuvent être stochastiques. Deuxièmement, pour le cas de plusieurs périodes sur problème de génération d'enchères avec ramassage et de livraison problème de fenêtres de temps, de profits et de demandes réservées et les délais de livraison, il sera intéressant de traiter les demandes sélectives classifiées pour lesquelles chaque période: si une demande sélective dans chaque catégorie ne peut être servie, il ne sera pas possible de servir toutes les demandes sélectives dans cette même catégorie. Dans un environnement de collaboration réaliste, il est parfois raisonnable d'ignorer un groupe de demandes pour réduire les coûts. Troisièmement, nous pouvons considérer l'effet de la réduction des émissions de CO2 à notre modèle dans le troisième problème. Bien qu'il soit important de réduire le délai de livraison pour satisfaire le client, l'émission de CO2 et l'augmentation des gaz à effet de serre dans l'environnement est une contrainte critique ces dernières années, car elle est devenue un problème majeur dans le monde et la plupart des pays développés prennent en compte des plans pour réduire les effets des émissions de CO2 dans l'atmosphère. Par conséquent, notre modèle pourrait inclure comme objectifs la réduction des émissions de CO2 en plus du coût et du profit. Enfin, les approches d'allocation des bénéfices n'ont pas été abordées dans cette thèse alors que ce sujet est nécessaire à la mise en oeuvre de la logistiques collaborative. Dans la littérature, le problème de la réattribution des demandes et celui de l'affectation des bénéfices sont souvent manipulés indépendamment. Il serait préférable que les deux problèmes puissent être examinés ensemble afin d'obtenir de meilleurs résultats qu'auparavant. Etudes sur le transport collaboratif : modèles et métaheuristiques Dans le domaine de la logistique collaborative, plusieurs transporteurs forment une alliance pour améliorer leurs opérations de transport et leur rentabilité en échangeant leurs demandes de transport. Dans cette thèse, nous concentrons sur la collaboration des transporteurs dans le transport de chargement partial (LTL). Plus précisément, trois sous-problèmes de la planification collaborative entre transporteurs sont pris en compte : un problème de planification centralisée de multitransporteurs avec ramassage et livraison, fenêtres de temps, demandes échangeables et demandes réservées, un problème de génération d'enchères à plusieurs périodes, un problème de ramassage et de livraison, fenêtres de temps, profits, demandes réservées et problème de génération d'enchères à plusieurs périodes avec prise en compte à la fois du coût et du délais de livraison. Ces sous-problèmes jouent un rôle essentiel dans la planification collaborative de transport entre transporteurs, mais dans la littérature, aucune étude profonde n'a été effectuée sur eux. Nous avons présenté de nouveaux modèles de programmation mathématique pour ces problèmes et développé des heuristiques efficaces pour obtenir des solutions proches de leurs optimums dans un temps de calcul raisonnable. Ces heuristiques proposées sont plus efficaces que le solveur commercial, CPLEX, non seulement en termes de qualité de solution mais aussi en termes de temps de calcul. Mots clés : transports routiers -recherche opérationnelle -métaheuristiques -transports urbainstransport durable -livraison de marchandises. precisely three sub-problems of collaborative planning are considered. Centralized multi-carrier problem with pickup and delivery, time windows, exchangeable requests and reserved requests, multi-period Bid Generation Problem with pickup and delivery problem, time windows, profits, reserved requests and multi period Bid Generation Problem with consideration of both cost and delivery lead time. These sub-problems play a vital role in collaborative transportation planning among carriers, but in the literature, there is no in-depth study on them. We have presented new mathematical programming models for these problems and developed efficient heuristics to obtain solutions close to their optimums in a reasonable computation time. The suggested heuristics are more efficient than commercial solver, CPLEX, not only in terms of solution quality but also in terms of computation time. Keywords: transportation, automotive -operations research -metaheuristics -urban transportationtransporation with time limitation -delivery of goods.

  paper, the principle of bidder's optimality in combinatorial bids is discussed. A fleet assignment model and the nearest insertion method are the two different heuristics are developed as solution methods. The BGP in collaborative transportation is suggested in[59]. In the problem, carriers by using VRP, operate BGP on the sets of lanes based on the actual routes. To solve the model, column generation and Lagrangian based methods are used. In[START_REF] Buer | An exact and two heuristic strategies for truthful bidding in combinatorial transport auctions[END_REF], two heuristic techniques and an exact strategy are developed to solve the bidding on the subsets of requests. The two

heuristic bidding approaches determine combination of promising request, use the capacitated p-median problem and save values by utilizing cooperation. The suggested heuristic techniques can assist a carrier to raise the chance of winning and can reduce the computational challenges in participation among carriers. About the exact bidding approach, it is a technique based on the combinations of elementary request. In the article, it is shown bidding on each elementary request combination is sufficient.

PICKUP AND DELIVERY REQUESTS WITH TIME WINDOWS, RESERVED REQUESTS AND EXCHANGEABLE REQUESTS

	C H A P T E R	3
	MULTI-CARRIERS

In this chapter, we, at first, present the background of Collaborative Logistics (CL) or Collaborative Transportation Management (CTM). Then we describe two types of horizontal collaborative logistics: Shipper collaboration and carrier collaboration. Furthermore, two types of transportation service are discussed. Truckload (TL) transportation and less-than-truckload (LTL) transportation are the two types of transportation service. In this thesis, we focus on carrier collaboration in LTL transportation, where two core sub-problems should be addressed. These sub-problems are: Collaborative transportation planning (CTP) problem and profit allocation problem. We mainly concentrate on CTP in this thesis. At last, a general literature review on CL and centralized planning approaches of CTP, and a detailed literature review on decentralized planning approaches of CTP are given to close the chapter.

  time Window for both pickup and delivery requests and reserved requests has not been studied in the literature. So, in this chapter, we try to fill this gap by presenting a mixed integer linear programming model to the problem and developing effective heuristic algorithms. We propose an Adaptive Large Neighborhood Search (ALNS) algorithm to solve which is successfully applied to solve various vehicle routing problems[START_REF] Ropke | An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows[END_REF]. In[65], an ALNS algorithm is applied to solve a pickup and delivery problem with time windows, profits, reserved requests, and involving a single carrier with a single vehicle depot. In that problem, it is not compulsory to serve all selective requests. The vehicle routing problem considered in this thesis is a new problem involving multi-carriers with multi-depots vehicle routing problem. Furthermore, each reserved request must be served by its own carrier and all requests must be served by all

Such a problem raises a new variant pickup and delivery requests with time windows (PDPTW), i.e. Multi-Carriers Pickup and Delivery requests with Time Windows and Reserved requests (MCPDPTWR). To the best of our knowledge centralized collaborative transportation planning in LTL among multi-carriers, where each request is a pickup and de-livery request with carriers. It means that, all exchangeable requests must be served by a carrier. Therefore, the existing ALNS algorithms cannot be directly applied to our problem and some adaptations of them are necessary in order to solve our problem. The ALNS proposed in this work uses a variety of destroy/ repair operators. Its search procedure consists of multiple phases, where different phases use different policies for the choice of requests to destroy (delete) or repair (re-insert). The basic idea is to alter the behavior of destroy/repair operators over successive phase of the ALNS;

Table 3 .1: Indices

 3 , sets, parameters for the mathematical model.

	Symbols	Description
	G = (V , E)	Complete directed graph G on which the studied problem is defined
	V	Set of all nodes
	E	Set of all edges
	n	Number of requests
	cr	Maximum number of carriers
	M	Set of carriers
	DC	Set of depot nodes of carriers
	p = {1, 2, .., n}	Set of pickup nodes, where the index of each pickup node i is the same as the
		index of its corresponding request i, i = 1, . . . , n
	D = {n + 1, ..., 2n} Set of delivery nodes of all requests, where n is the number of requests
	W	Set of nodes excluding the depot nodes of all carriers
	R = {1, .., n}	Set of requests that includes the subset of reserved requests R r and the
		subset of exchangeable requests R s
	R m r	Set of reserved requests of carrier m
	R s	Set of exchangeable requests
	Q	Vehicle capacity
	c i j	Traveling cost from node i to node j
	s i	Service time of node i
	K m = {1, .., V K m } Set of vehicles of carrier m, where V K m is the maximum number of vehicles
		of carrier m
	d n+i = -d i	Demand of the pickup node and the delivery node of request i, where d i is the
		demand of the pickup node and d n+i is the demand of the delivery node, d n+i
		is negative
	[e i , l i ]	Time window of node i, where e i is the lower bound of time window and l i is
		the upper bound of the time window
	t i, j

Table 3 .2: Decision

 3 variables for the mathematical model.

	Variables Description
	x i jkm	Binary variable equal to 1 if and only if vehicle k of carrier m uses edge (i, j)
	y ikm	Binary variable equal to 1 if and only if request i is served by vehicle k of carrier m
	U ikm	Arriving time of vehicle k of carrier m at node i
	L ikm	Load of vehicle k of carrier m when leaving from node i
	3

.2 Formal definition and mathematical model

	In our problem, there are multi-carriers with two types of requests: Reserved requests and
	exchangeable requests. The reserved requests of each carrier must be served by the carrier itself,
	whereas its exchangeable requests can be served by other carriers. The collaboration among
	carriers is realized by exchanging requests among them. Each carrier has a limited number
	of vehicles initially located at a depot. It is assumed that all vehicles are homogeneous. Each
	transportation request is a pickup and delivery request characterized by a pickup location with a
	time window, a delivery location with a time window too, a demand and an amount of revenue
	that can be generated for serving the request. The revenue of a request is the price paid by a
	customer (shipper) to a carrier serving the request. The objective of the problem is to optimally

Table 3 .3: The adjustment of scores. Score Condition for score increment

 3

	s 1	Finding a new best solution.
	s 2

Table 3 . 4 :

 34 The detailes information of simple example to implement GASA.

	Carrier1	Carrier2
	the index of the unique reserved	the index of the unique reserved
	request: 1	request: 3
	the pickup node index of the reserved	the pickup node index of the reserved
	request: 1	request: 3
	the delivery node index of the reserved	the delivery node index of the reserved
	request: 5	request: 7
	the index of the unique exchangeable	the index of the unique exchangeable
	request: 2	request: 4

the pickup node index of the exchangeable the pickup node index of the exchangrequest: 2 eable request: 4 the delivery node index of the exchangeable : 6 the delivery node index of the exchangrequest eable request: 8

Table 3 . 5 :

 35 Parameter values of ALNS determined empirically

	Parameter Description	Value
	nruns	Number of runs	12
	Q 1	Operator score increment case 1 10
	Q 2	Operator score increment case 2 5
	Q 3	Operator score increment case 3 3
	Q 4	Operator score increment case 4 1
	r f	Score reaction factor	0.8
	nse g	Number of phases	3000
	f r	Removal fraction	0.2

Table 3 . 6 :

 36 Parameter values of GASA and ITS determined empirically

	Parameter Description	Value
	SubI t	Number of iteration of SA 120
	µ m	Mutation rate	0.26
	nsp	Number of solution points 25

Table 3 . 7 :

 37 The domain of candidated parameters of GASA and ITS for calibration. The three proposed algorithms are compared with each other and with CPLEX based on all criteria defined in Table3.10, where Cost ALNS , Cost G AS A , and Cost ITS are the costs of the studied problem obtained by the three algorithms, respectively;

	Methodology Parameter	Range	Low Medium High
		N pop (Size of population)	100-200 100	150	200
	GASA	nI t (Maximum number of iterations) 200-600 200	400	600
		P c (Crossover probability)	0.4-0.8	0.4	0.6	0.8
		P m (Mutation probability)	0.05-0.3 0.05 0.175	0.3
		Tabu lists
		stl_X	0.2-0.5	0.2	0.35	0.5
	ITS	stl_Y	0.1-0.4	0.1	0.25	0.4
		stl_Z	0.1-0.5	0.2	0.35	0.5
		mni (Num of iteration)	50-100	50	75	100
	The time limitation is 3 hours for medium instances with 30 requests and 4 vehicles, and large
	instances with 50 requests and 8 vehicles.

UB M ILP and LB M ILP are the upper bound and the lower bound of the objective value of the problem obtained by CPLEX in a preset computation time.

Table 3 . 8 :

 38 The domain of candidated parameters of ALNS for calibration.

	Methodology Parameter	Range	Low(1) Medium(2) High(3)
		w (Start temperature control) 0.5-0.7	0.5	0.6	0.7
	ALNS	c (SA cooling factor)	0.9996-0.9998 0.9996	0.9997	0.9998
		nit	500-700	500	600	700

Table 3 . 9 :

 39 Parameter values of GASA determined by Taguchi.

	parameters npop P_c P_m Nit
	Value	150	0.6	0.05 800

Table 3 .

 3

	Value	0.5	0.25	0.2	100

10: Parameter values of ITS determined by Taguchi parameters stl_X stl_Y stl_Z mni

Table 3 .

 3

11: Criteria used for comparison of ALNS, ITS, GASA, and CPLEX.

Criterion Description

Gap M ILP

The relative gap between LB M ILP and UB M ILP defined as

(UB M ILP -LB M ILP ) LB M ILP

Gap ALNS

The relative gap between LB M ILP and Cost ALNS defined as (Cost ALNS -LB M ILP ) LB M ILP Gap G AS A The relative gap between LB M ILP and Cost G AS A defined as (Cost G AS A -LB M ILP ) LB M ILP Gap ITS The relative gap between LB M ILP and Cost ITS defined as (Cost ITS -LB M ILP ) LB M ILP by all algorithms, which are compared. An algorithm with minimum RPD value is supposed to be the most effective to solve the problem. RPD is formulated in the equation (3.25), where Criterion best and Criterion al g indicate the best value of a criterion obtained by all algorithms and the best value of the same criterion achieved by a considered algorithm correspondingly.

Table 3 . 12 :

 312 .[START_REF] Chao | The team orienteering problem[END_REF]. The results are analyzed at 95% confidence level. According to the table, null hypothesis is rejected. The rejection of null hypothesis declares there are significant differences among ALNS and ITS, ALNS, and GASA algorithms. Computational results of ALNS, ITS, GASA and CPLEX -part one

	R PD al g (Criterion) = |	Criterion best -Criterion al g Criterion best	| × 100		(3.25)
	Instance Number LB M ILP	UB M ILP Cost ALNS Cost ITS	Cost G AS A
	3×5×2 instances
	1	707.343	707.343	707.343	707.343	707.343
	2	556.776	556.776	556.776	556.776	556.776
	3	649.908	649.908	649.908	649.908	649.908
	4	545.779	545.779	545.779	545.779	545.779
	5	592.725	592.725	592.725	592.725	592.725
	6	690.334	690.334	690.334	690.334	690.334
	7	645.825	645.825	645.825	645.825	645.825
	8	632.609	632.609	632.609	632.609	632.609
	9	597.151	597.151	597.151	597.151	597.151
		573.451	573.451	573.451	573.451	573.451
	3×8×2 instances
		1006.084 1022.831 1009.361	1009.361 1009.361
		949.505	1030.405 962.535	963.279	963.038
		868.533	1018.795 875.608	875.676	875.670
		1085.425 1156.400 1094.486	1095.472 1095.255
		885.501	-	894.517	905.971	900.100
		824.222	-	852.645	854.515	853.211
		939.638	-	955.521	968.100	959.131
		892.157	1024.313 902.816	910.393	909.308
		968.684	-	990.001	1001.646 997.164
		898.9721 1013.951 915.531	917.503	916.845
	3×15×4 instances
		1721.373 2055.101 1755.073	1772.496 1770.922
		1620.219 -	1693.407	1748.906 1723.664
		1723.603 -	1791.902	1813.741 1808.142
		1812.100 -	1885.538	1911.649 1891.535
		1685.278 -	1758.043	1787.043 1779.101
		1628.011 -	1702.668	1749.865 1726.273

Table 3 .13: Computational

 3

	Instance Number CPU CPLE X (s) CPU ALNS CPU ITS CPU G AS A
	3×5×2 instances
	1	75.478	83.369	94.346	88.456
	2	68.521	84.109	96.893	89.825
	3	76.107	83.674	98.833	92.380
	4	68.733	84.223	96.021	87.958
	5	76.112	84.973	96.861	86.727
	6	75.207	84.123	97.362	89.033
	7	74.800	84.490	96.735	90.359
	8	75.564	85.274	96.587	90.874
	9	68.806	83.432	95.922	86.922
	10	68.225	83.549	91.278	87.224

results of ALNS, ITS, GASA and CPLEX -computation time.

Table 3 .

 3

14: Gap of ALNS, ITS, GASA and CPLEX.

Table 3 . 15 :

 315 Computational results (RPD) of ALNS, ITS and GASA.

	3256	0.325	1.664	0.325
	1.372	1.450	8.520	1.425
	0.814	0.822	17.300	0.821
	0.834	0.925	6.538	0.905
	1.018	2.311	-	1.648
	3.448	3.553	-	3.517
	1.690	3.029	-	2.074
	1.194	2.043	14.814	1.922
	2.200	3.402	-	2.940
	1.841	2.061	12.790	1.988

Table 3 . 16 :

 316 The results of ANOVA test over the RPD of objective functions of algorithms.

	Source	DF SS	MS	F-test P-value Results
	ALNS,ITS	1	32.52	32.52 11.96	0.001	Null hypothesis is rejected.
	Error	98	266.38 2.72
	Total	99	298.90
	ALNS,GASA 1	25.44	25.44 9.43	0.003	Null hypothesis is rejected.
	Error	98	264.26 2.70
	Total	99	289.70
	GASA,ITS	1	0.43	0.43	0.38	0.540	Null hypothesis is not rejected.
	Error	98	112.20 1.14
	Total	99	112.63

Figure 3.11: Graphical comparisons of RPD for both algorithms on all test problems.

  this chapter, the collaborative transportation planning of multi-carriers with pickup and delivery requests with time windows has been studied. This problem has a new feature that each carrier has reserved requests, which must be self-served. We have proposed a mixed integer linear programming model for the problem. Because the model is NP-hard, it is impossible to get a feasible solution in a reasonable computation time for large instances. For this reason, we have proposed three metaheuristic algorithms, ALNS, ITS and, GASA, to solve the model. Numerical experiments on benchmark instances with RPD index show that the algorithms can obtain optimal solutions for small instances and ALNS can obtain better solutions for medium to large instances compared with GASA and ITS, whereas CPLEX cannot find even a feasible solution for medium and large instances in the allocated computation time. Moreover, we compared ITS

and GASA with RPD index. Statistical analysis indicated GASA can obtain a better solution by comparing ITS in a smaller running time.

  Constraint (4.1) ensures when a vehicle arrives at a node in a period, it must leave from the node in the same period. Constraints (4.2) and (4.3) signify each vehicle leaves its depot in a period must return to the depot in the same period. Equation (4.4) implies each reserved request must

	be served in its pre-specified period. Equation (4.5) indicates each selective request can be served
	in a period within its service period window or not served. Constraints (4.6) and (4.7) guarantee
	if a request is served in a period, its delivery node must be visited after its pickup node with
	the same vehicle in the same period. Equations (4.8)-(4.11) specify time windows constraints on

the pickup and delivery nodes of each request and the constraint on the maximum duration of each route. Constraints (4.12)-(4.13) ensure vehicle capacity constraints. Equations (4.14)-(4.17) describe the variables.

Table 4

 4 .1 and a solution of the instance is given in Table 4.2 and Table 4.3, where four requests are served in day 1 and day 2 and no request is served in day 3. The chromosome represented by three vectors X , Y , and Z for this solution is given in Fig 4.1:

Table 4 . 1 :

 41 Data of a simple instance.

	Small instance Data	Value
	Number of periods	3 days
	Number of requests	4 requests
	Number of pickup nodes	4 nodes
	Number of delivery nodes	4 nodes
	Total number of customer nodes	8 nodes
	Reserved requests	{3,4}
	Selective requests	{1,2}
	Prespecified period for serving each reserved request 3, day 1 and 4, day 2
	Service period window for each selective request	1, day [2,3] and 2, day [1,3]
	Index of pickup node of request i	As the same as its request
	Index of delivery node of request i	i + number of requests
	Number of vehicles available in each period	2 vehicles

Table 4 . 2 :

 42 The data for selective and reserved requests served in the first day.

reserved requests and selective requests served in day 1 Value

	4.3. METAHEURISTIC APPROACHES TO SOLVE MULTI-PERIODS BID GENERATION
		PROBLEM
	Index of reserved request served	3
	Pickup node index of reserved request	3
	Delivery node index of reserved request	7
	Index of vehicle used to serve the reserved request	1
	Index of selective request served	2
	Pickup node index of selective request	2
	Delivery node index of selective request	6
	Index of vehicle use to serve the selective request	1
	56

Table 4 . 3 :

 43 The data for selective and reserved requests served in the second day.

reserved requests and selective requests served in day 2 Value

	Index of reserved request served	4
	Pickup node index of reserved request	4
	Delivery node index of reserved request	8
	Index of vehicle used to serve the reserved request	2
	Index of selective request served	1
	Pickup node index of selective request	1
	Delivery node index of selective request	5
	Index of vehicle used to serve the selective request	2

Table 4 . 4 :

 44 The comparison of GA and BBO.

	BBO

Table 4 . 6 :

 46 The domain of calibrated parameters of GASA and BBO.

	Methodology Parameter Range	Low(1) Medium(2) High(3)
		Npop	400-600	400	500	600
	GASA	nIt	450-800	450	625	800
		Pc	0.4-0.8	0.4	0.6	0.8
		Pm	0.05-0.3	0.05	0.175	0.3
	BBO	E	1-2	1	1.5	2
		I	1-2	1	1.5	2
		Mmax	0.05-0.15 0.05	0.1	0.15
		Npop	200-300	200	250	300
		nIt	450-800	450	625	800
		Keep	0.15-0.25 0.15	0.2	0.25

Table 4 . 7 :

 47 Parameter values of GASA determined by Taguchi.

	Methodology Parameter Description	Value
		Npop	Population size	150
		nIt	Number of iterations 800
	GA	P c	Crossover probability 0.6
		P m	Mutation probability 0.05

Table 4 . 8

 48

	Methodology Parameter Description	Value
		E	Emigration rate	1
		I	Immigration rate	2
	BBO	M max	Mutation probability 0.05
		npop	Population size	200
		nIt	Number of iterations 800
		Keep	Elitism parameter	0.25
	of these factors on their performance evaluation, each algorithm is executed three times for
	each instance. The average profit and the average running time (in seconds) obtained by the
	three executions are reported. For CPLEX, since the considered carrier collaboration problem is
	NP-hard [66], it is very time consuming to solve optimally medium size and large size instances.
	For this reason, we set a maximum running time for CPLEX to solve each medium or large size
	instance. The time limitation is 2 hours for each medium size instance with 20 requests and 30
	requests 4 hours for each large size instance with 40, 50 and 100 requests. Our two proposed
	algorithms are compared with each other and with CPLEX based on criteria defined in

: Parameter values of BBO determined by Taguchi.

Table 4 .

 4 [START_REF] Chen | Mathematical model and solution approach for collaborative logistics in less than truckload (LTL) transportation[END_REF], where Ob j G AS A and Ob j BBO are the profits of the studied problem obtained by the two algorithms, respectively; UB M ILP and LB M ILP are the upper bound and the lower bound of the This may be because using diversification and intensification operators by using SA in GASA, which makes it able to search diversified regions in the solution space.

objective value of the problem obtained by CPLEX in the preset running time.

The computation results are given in

Table 4.10, Table 4.11, and Table 4.12. From Table 4.10 and Table 4.11, we can see, for small 6 requests instances, CPLEX, GASA, and BBO all can find outperforms BBO.

Table 4 . 10 :

 410 Computational results of GASA, BBO, and CPLEX -part one.

	Instance Number	LB M ILP	UB M ILP	Ob j G AS A	Ob j BBO
	6 request instances (small instance)
	6-3-3	256.525	265.525	265.525	256.525
	8 request instances (small instances)
	8-4-4	512.015	514.731	514.682	513.373
	10 request instances (small instances)
	10-5-5a	909.810	984.660	979.614	972.828
	10-5-5b	968.6747 1011.463	1008.415	991.473
	10-5-5c	974.001	1028.626	1019.693	1009.930
	10-3-7d	1125.153 1157.164	1148.267	1138.231
	10-3-7e	828.254	903.828	897.786	893.741
	10-3-7f	-	1210.611	1183.689	1179.442
	10-7-3g	917.419	936.1774	929.350	926.464
	10-7-3h	1266.383 1298.205	1286.358	1281.631
	10-7-3i	-	1375.914	1328.921	1314.160
	20 request instances (medium instances)
	20-10-10a	-	2619.785	2473.626	2461.335
	20-10-10b	-	2286.16	2194.358	2173.123
	20-10-10c	-	3815.445	3651.975	3609.450
	20-5-15d	1832.804 2015.517	1991.431	1988.117
	20-5-15e	-	2568.903	2462.240	2406.062
	20-5-15f	-	2819.162	2698.150	2673.227
	20-15-5g	-	3765.529	3577.579	3573.118
	20-15-5h	-	3324.128	3153.251	3131.662
	20-15-5i	-	4514.717	4278.305	4238.713
	30 request (medium instances)
	30-15-15c	-	7432.469	7003.483	6991.804
	30-10-20d	-	6629.284	6263.020	6150.135
	30-10-20e	-	8803.686	8249.580	8183.466
	30-10-20f	-	8217.720	7783.125	7694.472
	30-20-10g	-	11214.849 10452.390 10425.340
	30-20-10h	-	12717.674 11991.118 11940.267
	30-20-10i	-	11591.228 10783.710 10694.481

Table 4 . 11 :

 411 Gap of GASA, BBO, and CPLEX.

	Instance Number	Gap G AS A Gap BBO Gap M ILP
	6 request instances (small instance)
	6-3-3	0	0	0
	8 request instances (small instance)
	8-4-4	0.009	0.263	0.333
	10 request instances (small instances)
	10-5-5a	0.512	1.201	7.601
	10-5-5b	0.301	1.976	4.230
	10-5-5c	0.869	1.818	5.311
	10-3-7d	0.769	1.636	2.766
	10-3-7e	0.668	1.116	8.361
	10-3-7f	2.223	2.574	-
	10-7-3g	0.729	1.037	2.003
	10-7-3h	0.912	1.276	2.451
	10-7-3i	3.415	4.488	-
	20 request instances (medium instances)
	20-10-10a	5.579	6.048	-
	20-10-10b	4.015	4.944	-
	20-10-10c	4.284	5.398	-
	20-5-15d	1.195	1.359	9.065
	20-5-15e	4.1520	6.338	-
	20-5-15f	4.152	6.295	-
	20-15-5g	4.991	5.109	-
	20-15-5h	5.140	5.789	-
	20-15-5i	5.236	6.113	-

Table 4 . 12 :

 412 Computational time of GASA, BBO and CPLEX.

	Instance Number	CPU M ILP CPU G AS A CPU BBO
	6 request instances (small instances)
	6-3-3	67.649	85.117	89.216
	8 request instances (small instances)
	8-4-4	98.365	100.794	123.675
	10 request instances (small instances)
	10-5-5a	500	184.342	215.429
	10-5-5b	500	160.105	204.767
	10-5-5c	500	173.110	217.353
	10-3-7d	500	186.185	253.419
	10-3-7e	500	190.856	229.022
	10-3-7f	500	185.647	232.109
	10-7-3g	500	177.961	211.360
	10-7-3h	500	201.128	249.029
	10-7-3i	500	198.403	253.715
	20 request instances (medium instances)
	20-10-10a	3600	331.511	395.389
	20-10-10b	3600	343.992	416.356
	20-10-10c	3600	351.836	407.354
	20-5-15d	3600	326.537	402.911
	20-5-15e	3600	322.419	373.902
	20-5-15f	3600	335.395	411.363
	20-15-5g	3600	339.014	402.742
	20-15-5h	3600	346.191	413.808
	20-15-5i	3600	333.587	421.066

Table 4 . 13 :

 413 Computational result (RPD) of GASA and BBO.

	Instance Number RPD G AS A RPD BBO
	6-3-3	0	0
	8-4-4	0.002	0.047
	10-5-5a	0.115	0.631
	10-5-5b	0.481	1.079
	10-5-5c	0.111	1.054
	10-3-7d	0.854	1.069
	10-3-7e	0.679	1.238
	10-3-7f	0.582	1.032
	10-7-3g	0.704	1.081
	10-7-3h	0.617	1.151
	10-7-3i	0.329	1.141
	20-10-10a	1.089	1.827
	20-10-10b	1.015	1.619
	20-10-10c	1.049	1.665
	20-5-15d	1.128	1.866
	20-5-15e	0.114	1.030
	20-5-15f	0.938	1.169
	20-15-5g	1.477	1.981
	20-15-5h	1.283	1.961
	20-15-5i	1.359	1.809
	30-15-15c	1.284	1.802
	30-10-20d	1.216	1.732
	30-10-20e	1.346	1.910
	30-10-20f	1.103	1.937
	30-20-10g	1.117	1.885
	30-20-10h	1.246	1.862
	30-20-10i	1.599	2.033

Table 4 . 14 :

 414 The results of ANOVA test over the presented RPD for GASA and BBO.

	Source	DF SS	MS	F -test P -value R esults
	Algorithm 1	51.75	59.71 10.14	0.001	Null hypothesis is rejected
	Error	40	235.63 5.89
	Total	77	311.15

Table 5 . 2 :

 52 The decision variables of the considered model. If and only if vehicle k visits directly node j after node i in period h. y ikh = 1 If and only if request i is served by vehicle k in period h. U ikh Arriving time of vehicle k at node i in period h. CV ikh Load of vehicle k when it leaves node i in period h. y ikh

	Symbols Explanation
	x i jkh = 1

Table 5 . 3 :

 53 NSGA-II and NRGA parameter ranges and the levels of factors.

	Algorithm Parameter Description	Range	Low(1) Medium(2) High(3)
		Npop	Population size	50-200	50	125	200
	NRGA and nIt	Number of iterations 200-500 200	350	500
	NSGA-II	P c	Crossover probability 0.3-0.7	0.3	0.5	0.7
		P m	Mutation probability 0.1-0.5	0.1	0.3	0.5

Table 5 . 4 :

 54 Taguchi procedure for NSGA-II.

	Run Order Npop P c	P m nIt Response
	1	1	1	1	1	9.5048
	2	1	2	2	2	7.909
	3	1	3	3	3	10.206
	4	2	1	2	3	3.607
	5	2	2	3	1	3.586
	6	2	3	1	2	4.486
	7	3	1	3	2	8.280
	8	3	2	1	3	5.399
	9	3	3	2	1	13.877

Table 5 . 5 :

 55 Taguchi procedure for NRGA.

	Run Order Npop P c	P m nIt Response
	1	1	1	1	1	4.820
	2	1	2	2	2	1.470
	3	1	3	3	3	5.559
	4	2	1	2	3	8.603
	5	2	2	3	1	7.367
	6	2	3	1	2	5.767
	7	3	1	3	2	2.193
	8	3	2	1	3	13.993
	9	3	3	2	1	4.565

Table 5 . 7 :

 57 Computational results of GASA and ITS.

	Instance Number Ob j G AS A	Ob j ITS	LB M ILP	UB M ILP	Gap M ILP Gap G AS A Gap ITS
	20-10-10a	1356.511	1344.763	-	1429.288	-	5.091	5.913
	20-10-10b	1087.414	1070.291	967.511	1140.983	15.203	4.694	6.195
	20-10-10c	2592.257	2564.118	1964.131 2705.007	27.389	4.168	5.208
	20-5-15d	968.265	971.701	-	1017.989	-	4.884	4.547
	20-5-15e	996.798	985.357	-	1038.841	-	4.047	5.148
	20-5-15f	2572.020	2537.411	2214.212 2666.525	16.962	3.544	4.842
	20-15-5g	2271.493	2249.102	-	2349.265	-	3.310	4.263
	20-15-5h	1423.878	1420.825	-	1511.192	-	5.777	5.979
	20-15-5i	3778.519	3732.614	-	3967.039	-	4.752	5.909
	30-15-15c	5312.654	5197.674	-	5610.102	-	5.302	7.351
	30-15-15d	4985.130	4889.179	-	5311.148	-	6.138	7.944
	30-15-15e	6217.237	6055.472	-	6569.163	20.431	5.357	7.819
	30-15-15f	6373.191	6262.774	-	6728.334	-	5.278	6.919
	30-20-10g	8628.015	8644.162	-	9164.702	-	5.856	5.679
	30-20-10h	10415.620 10180.660 -	11040.900 -	5.663	7.791
	30-20-10i	9529.182	9337.791	-	10038.770 -	5.076	6.982
	40-20-20a	9632.193	9477.823	-	10520.107 -	8.440	9.908
	40-20-20b	10774.450 10851.256 -	11868.040 -	9.214	8.567
	40-20-20c	10616.947 10617.322 -	11697.518 -	9.237	9.234
	40-15-25d	8541.138	8386.904	-	9301.346	-	8.173	9.831
	40-15-25e	8046.854	7900.667	-	8821.121	-	8.777	10.434
	40-15-25f	10176.106 10091.119 -	11266.065 -	9.675	10.429
	40-25-15g	8590.802	8429.175	-	9386.584	-	8.477	10.198
	40-25-15h	11471.169 11209.378 -	12497.361 -	8.211	10.306
	40-25-15i	9781.714	9496.332	-	10755.698 -	9.055	11.708
	50-25-25a	18047.940 17663.351 -	20192.817 -	10.626	12.526
	50-25-25b	15050.833 14672.267 -	16743.635 -	10.110	12.371
	50-25-25c	12601.148 12512.386 -	14175.432 -	11.105	11.732
	50-20-30d	15131.713 14887.265 -	16932.874 -	10.637	12.081
	50-20-30e	16886.925 16838.288 -	19169.190 -	11.906	12.160
	50-20-30f	14833.207 14600.436 -	16867.276 -	12.059	13.440
	50-30-20g	11594.018 11517.593 -	13008.477 -	10.873	11.461
	50-30-20h	16011.674 15594.412 -	17814.653 -	10.121	12.463
	50-30-20i	11920.136 11876.153 -	13497.751 -	11.687	12.013

Table 5 . 8 :

 58 Computational results (RPD) and computation time of GASA and ITSInstance Number RPD G AS A RPD ITS CPU G AS A CPU ITS

	20-10-10a	1.603	1.977	431.555	504.792
	20-10-10b	0.528	1.256	429.222	503.326
	20-10-10c	1.800	2.572	430.770	504.344
	20-5-15d	1.523	2.837	428.317	504.120
	20-5-15e	1.837	1.243	452.568	546.661
	20-5-15f	0.185	1.569	459.527	544.775
	20-15-5g	0.402	1.843	468.733	588.079
	20-15-5h	1.594	3.265	464.176	585.230
	20-15-5i	1.275	2.016	473.551	589.345
	30-15-15c	1.082	2.896	503.737	611.280
	30-10-15d	1.123	2.124	505.5621	596.051
	30-10-15e	2.882	2.853	521.853	614.605
	30-10-20f	1.786	2.980	536.869	628.074
	30-20-10g	1.929	2.909	534.912	627.562
	30-20-10g	1.720	3.020	538.414	641.857
	30-20-10g	1.647	2.615	548.990	655.382
	40-20-20a	2.833	4.190	840.096	969.553
	40-20-20b	1.772	3.604	851.147	975.242
	40-20-20c	2.088	4.657	837.539	973.140
	40-15-25d	2.521	4.242	842.808	974.931
	40-15-25e	2.438	3.895	856.658	982.990
	40-15-25f	2.565	3.367	869.731	980.407
	40-25-15g	2.652	4.615	872.548	983.625
	40-25-15h	1.000	3.481	874.772	985.922
	40-25-15i	2.442	4.927	882.646	986.164
	50-25-25a	2.375	3.173	1718.932	1983.595
	50-25-25b	2.563	5.710	1723.169	1984.144
	50-25-25c	2.104	4.906	1808.709	2007.163
	50-20-30d	3.861	5.986	1775.111	1940.328

Table 5 . 9 :

 59 The results of ANOVA test over the presented single objective mathematical model.

	Source	DF SS	MS	F -test P -value R esults
	Algorithm 1	51.75	51.75 15.16	0.000	Null hypothesis is rejected
	Error	76	259.40 3.41
	Total	77	311.15

Table 5 . 10 :

 510 Multi-objective metrics computed for NRGA

	Instance Number D iversit y NOS	M ID	S pacing T ime
	6-3-3	14.787	2.765	0.039	4.022	14.677
	8-4-4	24.915	30.377 0.030	13.414	1.312
	10-5-5a	49.138	13.529 2.650	6.321	6.182
	10-5-5b	47.287	13.905 0.001	10.975	3.664
	10-5-5c	50.960	42	12.517 40.538	1.589
	10-3-7d	19.603	6.529	15.652 28.847	6.821

Table 5 . 11 :

 511 Multi-objective metrics computed for NSGA-II

	Instance Number D iversit y NOS	M ID	S pacing T ime
	6-3-3	16.628	7.439	1.260	2.298	22.114
	8-4-4	0.508	0.003	0.003	10.365	0.207
	10-5-5a	98.211	4.059	0.086	3.723	0.431
	10-5-5b	94.525	4.882	0.523	3.658	0.338
	10-5-5c	36.161	38	8.986	48.406	0.088
	10-3-7d	64.842	45.652 17.384 31.538	0.288
	10-3-7e	49.013	3.609	30.024 52.563	1.891
	10-3-7f	38.134	2.167	46.29	40.808	0.643
	10-7-3g	39.718	43	24.235 83.379	0.970
	10-7-3h	35.543	26	98.635 23.976	0.827
	10-7-3i	5.292	6	4.769	60.365	0.930
	20-10-10a	39.163	3.301	29.787 49.504	0.968
	20-10-10b	28.387	2.038	18.778 48.524	0.506
	20-10-10c	27.198	27	0.280	26.573	0.347
	20-5-15d	14.095	38	0.252	63.679	0.888
	20-5-15e	25.717	22	1.299	18.680	0.412
	20-5-15f	43.305	6	0.721	29.429	0.722
	20-15-5g	44.338	6.310	9.687	88.088	23.104
	20-15-5h	20.965	5.859	1.618	1.944	30.746
	20-15-5i	6.966	25.336 0.751	11.283	0.395
	30-15-15c	2.941	5.730	0.190	18.768	30.565
	30-10-20d	35.602	9	1.656	17.545	29.959
	30-10-20e	48.791	26.666 4.040	0.817	23.887
	30-10-20f	29.322	34.444 0.906	0.462	30.480
	30-20-10g	7.276	14.255 0.039	1.135	28.911

Table 5 . 12 :

 512 The results of ANOVA test over the studied bi-objective mathematical model.

	M etrics	Source	DF SS	MS	F -test P -value R esults
		Algorithm 1	1430	1430	4.40	0.038
	M ID	Error	106 34444	325	Null hypothesis is rejected
		Total	107 35874
		Algorithm 1	962	962	5.32	0.023
	T ime	Error	106 19162	181	Null hypothesis is rejected
		Total	107 20124
		Algorithm 1	28276	28276 1.86	0.175
	S pacing	Error	106 1611068 15199	Null hypothesis is not rejected
		Total	107 20124
		Algorithm 1	1200	1200	5.48	0.021
	NOS	Error	106 23198	219	Null hypothesis is rejected
		Total	107 24398
		Algorithm 1	26426	26426 1.81	0.182
	D iversit y Error	106 1550063 14623	Null hypothesis is not rejected
		Total	107 1576488

2 Problème de ramassage et de livraison avec plusieurs transporteurs, fenêtres de temps, demandes réservées et demandes échangeables

  . Dans cette thèse, nous étudions le problème de la collaboration entre les transporteurs dans le service de ramassage et de livraison avec différentes spécifications (fenêtres de temps, bénéfices, demandes réservées, concept périodique et en supposant deux fonctions objectifs dans le Chapitre (5) où le transport de chargement partial est pris en compte dans le cadre de l'initiative centralisée de transport de lots brisés et des approches décentralisées. En effet, le problème de collaboration entre transporteurs dans le service de ramassage et de livraison avec des fenêtres de temps a attiré beaucoup d'attention au cours des dernières années avec un attrait particulier à l'objectif de la planification opérationnelle dans les réseaux logistiques. Dans le logistique collaborative avec ramassage et livraison, chaque demande est définie par deux emplacements, la ramassage et la livraison, De plus, chaque point a une fenêtre de temps. Dans un premier temps, chaque transporteur est rémunéré par les expéditeurs (clients). Chaque transporteur établit un plan pour répondre aux demandes qu'il reçoit au moyen de ses propres véhicules et de la pré-collaboration. Au final, le rapport coût/bénéfice peut être calculé. Certaines demandes (appelé aussi demandes spéciales) sont aussi livrées en collaboration avec d'autres transporteurs. En plus, les transporteurs puvent aussi émettre des demandes d'échanges de livraison des biens (appelé demande d'échange). De ce fait, dans la collaboration, toutes les demandes partagées de tous les transporteurs sont cumulées. Par conséquent, deux approches notables sont utilisées pour résoudre le problème du logistique collaborative avec ramassage et livraison dans cette thèse: Avec l'apparition et le développement ces dernières années de Fourth-Party Logistics (4PL), les fournisseurs agissent à titre d'intégrateur et coordonnent la planification du transport sans un échange direct de données. De ce fait, cette préoccupation de partage de données est évitée. De plus, il est possible, digne pour un transporteur de révéler certaines informations aux (4PL) en échange d'une augmentation de profit. Une telle approche de planification centralisée a également été utilisée dans le transport collaboratif, notamment dans le commerce tel que le commerce de services dans le domaine de la logistiques du commerce électronique inter-entreprises [79]. Dans cette thèse, deux types d'approches de planification concertée des transports sont proposés pour résoudre les problèmes cités précédemment. L'une est une approche décentralisée et utilisant le problème de la génération de soumissions, l'autre est l'approche de planification centralisée. 1. Dans l'ensemble, l'approche de planification centralisée peut permettre d'obtenir un meilleur rendement en matière de collaboration entre plusieurs transporteurs avec des lots brisés. Dans la planification collaborative centralisée des transports, où chaque transporteur dispose d'un nombre limité de véhicules et chaque demande est une demande de ramassage et de livraison dans les fenêtres de temps spécifiées. Dans ce cas, chaque transporteur Dans le problème, il existe deux types de demandes différentes, les demandes réservées du transporteur et des demandes sélectives. Le transporteur s'engage par contrat avec ses expéditeurs à servir tous les clients par lui-même. Les demandes sélectives sont proposées par d'autres transporteurs et elles sont ouvertes aux soumissions des transporteurs. Chaque demande comporte une demande de ramassage et de livraison avec un point de ramassage, un point de livraison, une quantité de ramassage et de livraison et deux fenêtres de temps.Le temps de livraison spécifie la période la plus rapprochée et la dernière période de traitement de la demande, tandis que l'intervalle de temps affiche l'heure de service la plus ancienne et la plus récente et elle est affectée aux deux points de ramassage et de livraison. En outre, un bénéfice est associé à chaque demande sélective qui est le prix de la demande fournie par un expéditeur. En incluant le concept périodique dans la CA (enchères combinatoires), le transporteur peut planifier ses opérations de transport à l'avance et dans un horizon mobile. De ce fait, un transporteur doit prendre deux décisions importantes dans le BGP: Quelles demandes sélectives sont choisies? La seconde est de déterminer Le deuxième avantage de la réduction de délai de livraison est le choix des transporteurs en fonction de facteurs géographiques. Dans de nombreuses acquisitions, bien que le coût soit un facteur important dans l'évaluation des commandes, les transporteurs se soucient de ce qui suit sur les spécifications de qualité lors de l'estimation des commandes passées par les fournisseurs[START_REF] Hu | Transportation service procurement problem with transit time[END_REF]. En effet, en considérant le délai de livraison court, le commissaire-priseur s'implique aussi dans d'autres facteurs que les coûts. Dans de nombreuses situations d'acquisition, bien que le coût soit un attribut important dans l'évaluation des commandes, les transporteurs se soucient des spécifications de qualité lors de l'estimation des commandes passées par les fournisseurs[START_REF] Ghosh | Scoring auctions: A brief survey[END_REF]. Dans le travail actuel, l'objet du service de transport est de maximiser les avantages totaux et de réduire au minimum le délai de livraison total présenté dans le (Chapitre 5). Cet objectif peut se répartir de la manière suivante: Depuis que les algorithmes évolutionnaires travaillent sur la population de solutions, ils sont bien adaptés aux problèmes multiobjectifs. Lors de leur conception, deux objectifs sont pris en compte: ils doivent atteindre la frontière de Pareto, ils doivent aussi trouver toutes les solutions le long de Le ALNS a été utilisé avec succès pour résoudre divers problèmes de routage de véhicules[START_REF] Pisinger | A general heuristic for vehicle routing problems[END_REF]. Dans [65], un algorithme ALNS est appliqué pour résoudre un problème de ramassage et de livraison avec des fenêtre de temps, des profits, des demandes réservées et impliquant un seul transporteur avec un seul dépôt de véhicules. Dans ce problème, il n'est pas obligatoire de répondre à toutes les demandes sélectives. Le problème de tournées de véhicules examiné dans le présent document est un nouveau problème qui concerne plusieurs transporteurs et plusieurs dépôts de véhicules. De plus, chaque demande réservée doit être servie par son propre transporteur et toutes les demandes doivent être servies par tous les transporteurs, les algorithmes ALNS existants ne peuvent pas être appliqués directement à notre problème, certaines adaptations sont nécessaires afin de résoudre notre problème. Le ALNS proposé dans le présent document fait appel à divers opérateurs de destruction/réparation. Sa procédure de recherche se compose de plusieurs phases, où différentes phases utilisent différentes FENÊTRES DE TEMPS, DEMANDES RÉSERVÉES ET DEMANDES ÉCHANGEABLES politiques pour le choix des demandes de destruction (suppression) ou de réparation (réinsertion). L'idée de base est de modifier le comportement des opérateurs de destruction/réparation au cours d'une phase successive de l'ALNS afin qu'il puisse explorer diverses régions. De plus, une postoptimisation basée sur la recherche locale est appliquée à la fin de chaque phase afin d'améliorer encore la qualité de la solution finale obtenue par l'ALNS. A des fins de comparaison, nous développons également une approche de recherche Tabu améliorée. Cette approche améliore la recherche tabu classique en conservant de multiples solutions pendant le processus de recherche, en collectant et en utilisant leurs informations afin d'améliorer plus rapidement la solution actuelle[75]. De plus, nous utilisons une tactique de mutation qui est une autre technique pour améliorer la performance de cet algorithme[START_REF] Jia | An improved tabu search approach to vehicle routing problem[END_REF].

	la frontière. C'est un problème d'intensification et de diversification, et il existe certains
	Enfin, l'objectif de la deuxième approche est de réduire le délai de livraison (temps de transit mécanismes pour traiter les problèmes suivants ces objectifs. Par conséquent, deux
	du transport) en plus de maximiser les profits. Cela signifie que le problème bi-objectif doit être algorithmes basés sur la population, NSGAII et NRGA, sont les solveurs appliqués
	résolu. Par conséquent, on a définit un modèle mathématique bi-objectif que l'on va résoudre avec pour résoudre le modèle mathématique bi-objectif suggéré pour les soumissions à
	des algorithmes bi-objectifs appropriés. périodes multiples.
	A.1 Les contributions de la thèse
	La première approche consiste à réaffecter un ensemble de demandes échangeables au
	moyen d'une approche centralisée pour faire une planification collaborative des transports et
	les desservir ensuite par des tours à chaque transporteur en prenant en compte ses contraintes peut réserver des demandes qui doivent être en libre-service. En échangeant certaines
	de disponibilité de ressources. Dans ce cas, le problème est d'abord formulé par le biais d'une demandes entre eux, une telle collaboration peut les aider à réduire les coûts de transport
	approche centralisée en échangeant des demandes entre les transporteurs. Ensuite, en présentant et augmenter leurs profits. Cette approche peut être réalisée par l'intermédiaire d'une
	Quatrième Partie Prestataire logistiques (4PL) qui agit en tant qu'intégrateur coordonnant le modèle mathématique, le problème est résolu par des algorithmes métaheuristiques. Un croisement et un des opérateurs de mutation bien adaptés à la structure chromosomique la planification du transport entre les transporteurs. Un modèle de programmation linéaire La seconde est une approche de planification décentralisée qui nécessite l'utilisation de (BGP) sont utilisés. Cette méthode utilise l'algorithme basé sur la population et l'algorithme du à nombres entiers mixtes (MILP) est formulé pour ce problème. Étant donné que le modèle pour sa résolution. Dans ce problème, il y a deux demandes différentes: les demandes réservées point unique à la diversification et l'intensification de la solution séquentiellement. A des est NP-difficile, une recherche adaptative de grand quartier (Adaptive Large Neighborhood à chaque transporteur et les demandes sélectives. Chaque demande sélective est associée à fins de comparaison, nous utilisons également un algorithme d'optimisation basé sur la Search-ALNS) l'algorithme génétique hybride avec recuit simulé (GASA) et un algorithme un bénéfice qui est le prix de la demande fournie par un expéditeur. En incluant un concept périodique, le transporteur peut planifier ses opérations de transport à l'avance et dans l'horizon temporel. En comparant les deux approches, l'approche décentralisée permet de préserver l'autonomie décisionnelle et les données métier ainsi que la confidentialité de chaque transporteur. Aussi, le bénéfice total de tous les transporteurs généré par le système centralisé est généralement plus élevé que celui généré par l'approche décentralisée, ceci est dû en raison de l'importance de l'approche décentralisée. La principale préoccupation de l'utilisation d'un système centralisé con-siste à préserver la confidentialité des données commerciales échangées entre les transporteurs. biogéographie (BBO) qui est un algorithme basé sur la population et dont ses spécifications amélioré de La recherche Tabu (ITS) pour résoudre le modèle. Le ALNS utilise une variété quelles demandes sélectives dans quelles périodes sont servies en plus des demandes sont proches de l'GA et son fonctionnement est sur la population de solutions pour trouver de méthodes de destruction et d'élimination. Les opérateurs de réparation, les multiples réservées afin de maximiser le profit total. Un modèle de programmation linéaire mixte la meilleure solution au problème. En comparant GA et BBO, chaque chromosome dans phases de recherche et la post-optimisation est basée sur la recherche locale, le GASA (MILP) est proposé au problème. Le problème est NP-difficile et pour résoudre les l'GA, qui est considérée comme une personne ayant une valeur de condition physique, est profite des avantages de l'algorithme génétique et du recuit simulé (d'une part, le critère grandes instances, deux algorithmes métaheuristiques sont suggérés, une combinaison un habitat convenable qui est appelé HSI (Indice de qualité de l'habitat, cet indice est démographique ajoute la diversification et d'autre part, la caractéristique de recherche d'Algorithme Génétique et de Recuit simulé (GASA) et recherche Tabu améliorée (ITS). présenté dans le Chapitre 4). locale par l'application de l'AS permet d'éviter d'être piégé dans l'optimum local). Le TS • Bi-objectif: En fait, problème de génération d'enchères à périodes multiples et à amélioré (ITS) adopte un opérateur de mutation et conserve de multiples solutions pendant 3. Dans les entreprises, en plus de minimiser tous les coûts, l'expéditeur est intéressé par objectifs multiples maximiser les profits et réduire les délais de livraison (temps de la durée de vie de l'équipement. Le processus de recherche afin d'obtenir une meilleure solution plus rapidement est présenté dans le (Chapitre 3). la réduction des délais de livraison. La réduction des délais de livraison présente deux transit) [48]. Les deux fonctions objectives visant à minimiser le temps de transit

2. Un problème de génération d'enchères sur plusieurs périodes (BGP) pour un transporteur peut être pris en compte dans la logistiques collaborative avec ramassage et livraison. l'intervalle de temps de chaque requête sélective sélectionnée pour construire les routes afin de maximiser le profit total. Il en résulte un nouveau problème de ramassage et de livraison périodiques avec les fenêtres de temps, les profits et les demandes réservées. Donc, ce problème est un problème différent de celui présenté dans [65] qui considère les BGP à période unique. Selon

[START_REF] Dai | Price-setting based combinatorial auction approach for carrier collaboration with pickup and delivery requests[END_REF]

, le présent problème est NP-difficile et il est impossible d'obtenir des solutions réalisables ainsi qu'une solution optimale pour les grandes instances en utilisant un solveur commercial comme CPLEX. Ainsi, une approche hybride qui combine un algorithme génétique et un recuit simulé (dénommé « GASA») est proposée pour résoudre la problématique. Le GASA adopte une structure chromosomique spécifique à un problème. avantages: D'abord, des délais de livraison plus courts permettent une gestion agile de la chaîne d'approvisionnement et l'exécution des commandes est accélérée. Ainsi, elle améliore la capacité des expéditeurs à être concurrentiels dans l'industrie.

• Un objectif unique: On peut noter dans la théorie traditionnelle de la passation de marchés standard des enchères que, le commissaire-priseur ne se soucie que du prix de l'objet, mais pas d'autres attributs. Toutefois, dans de nombreuses situations d'approvisionnement, l'acheteur se soucie de certains attributs autres que le prix lors de l'évaluation des offres soumises par les fournisseurs. On peut trouver parmi les contraintes non monétaires qui préocuppent les acheteurs la qualité ou le temps nécessaire à la livraison. En d'autres termes, les expéditeurs s'inquiètent aussi des délais de livraison. Ce délai indique un meilleur service de transport. Dans ce problème, les transporteurs recherchent des demandes de transport par le biais d'enchères combinatoires au cours de chaque période qui représente la fenêtre de demandes sélectives. En plus des demandes réservées pour maximiser le profit total et d'autre part, le délai de livraison doit être réduit. Chaque demande sélective a des fenêtre de temps qui décrivent les heures de ramassage et de livraison valides et la fenêtre de période indiquant la période la plus rapprochée et la période la plus éloignée pour répondre à la demande sélective, tandis que chaque demande réservée doit être délivrée dans un une période préétabli. L'objectif du problème est de décider et à maximiser les profits sont contradictoires et sont donc considérées séparément. Résoudre un problème multi-objectifs signifie qu'on doit trouver un ensemble de solutions appelées frontière de Pareto.

A.

Dans le présent document, nous mettons l'accent sur la planification concertée du transport (CTP) entre les transporteurs dans un environnement de transport de lots brisés, où chaque demande est une demande de ramassage et de livraison avec fenêtre de temps pour les points de ramassage et de livraison. Chaque transporteur peut avoir des demandes réservées, qui doivent être en libre-service, et la collaboration entre les transporteurs est réalisée par l'échange de demandes sans réserve (appelées ci-après demandes échangeables) entre eux. Nous adoptons une approche de planification centralisée pour le problème et ce dernier devient un problème de ramassage et de livraison par plusieurs transporteurs avec des fenêtres de temps, deux types différents de demandes, des demandes échangeables et réservées, ce qui est une nouvelle variante du problème NP-difficile de tournées des véhicules

[START_REF] Verdonck | Collaborative logistics from the perspective of road transportation companies[END_REF]

. Malgré le problème d'orientation où il n'y a pas d'obligation de répondre à toutes les demandes

[START_REF] Boussier | An exact algorithm for team orienteering problems[END_REF]

, dans notre problème toutes les demandes échangeables doivent être traitées. Après avoir présenté un modèle de programmation linéaire d'entiers mixtes au problème, nous proposons un algorithme ALNS (Adaptive Large Neighborhood Search) pour le résoudre.

A.2.

1 Description et Formulation du Problème

	min m∈M i∈V j∈V k∈K m c i j x i jkm
	tel que:
	x jikm -
	j∈V , j =i

Il y a plusieurs transporteurs avec deux types de demandes: les demandes réservées et les demandes échangeables. Les demandes réservées de chaque transporteur doivent être servies par le transporteur lui-même, tandis que ses demandes échangeables peuvent être servies par d'autres transporteurs. La collaboration entre les transporteurs est réalisée par l'échange de demandes entre eux. Chaque transporteur dispose d'un nombre limité de véhicules situés initialement dans un dépôt. On suppose que tous les véhicules sont homogènes. Chaque ordre de transport est un ordre de ramassage et de livraison caractérisé par un lieu de ramassage avec une fenêtre de temps, un lieu de livraison avec une fenêtre de temps également, une demande et un montant de recettes qui peut être généré pour répondre à l'ordre. Aussi, le revenu d'une demande est le prix payé par un client (expéditeur) à un transporteur qui répond à sa demande. L'objectif du problème est de réaffecter de façon optimale toutes les demandes échangeables entre les transporteurs afin de maximiser leur profit total ou, de façon équivalente, de minimiser leur coût total de transport pour répondre à toutes les demandes réservées et échangeables. Nous adoptons une approche centralisée pour résoudre ce problème. De ce fait, nous formulons d'abord ce problème comme un MILP. Le Tableau A.1 et Tableau A.2 énumère les indices, les paramètres, les ensembles, les variables de décision utilisés dans le modèle. j∈V ; j =i

3 Problème de génération d'enchères sur plusieurs périodes avec demandes de ramassage et de livraison, profits et demandes réservées

  22)L'objectif est de minimiser le coût total de transport de tous les transporteurs. La contrainte (A.1) est l'équation de préservation du flux et décrit chaque véhicule qui arrive à un noeud client et doit le quitter. L'équation (A.2) décrit que chaque noeud client est visité exactement une fois par les véhicules. Les contraintes (A.3)-(A.6) indiquent pour chaque transporteur le moment où chaque véhicule quitte son dépôt et doit retourner au même dépôt. Les contraintes (A.7)-(A.9) La fenêtre de période spécifie l'intervalle dans lequel la demande doit être DEMANDES DE RAMASSAGE ET DE LIVRAISON, PROFITS ET DEMANDES RÉSERVÉES exécutée, tandis que la fenêtre de temps affiche l'intervalle horaire affecté à la fois au point de ramassage et au point de livraison. De plus, chaque demande sélective est associée à un profit qui est le prix de service de la demande fournie par un expéditeur. En incluant le concept périodique dans l'AC, le transporteur peut planifier ses opérations de transport à l'avance et de façon horizontale. Un transporteur doit prendre deux décisions importantes dans le BGP: quelles demandes sont choisies pour enchère et servir dans leurs fenêtres de période de service et comment les routes sont construites pour maximiser son profit total. Cela entraîne un nouveau problème de ramassage et de livraison périodiques avec les fenêtres de temps, les profits et les demandes réservées. Ce problème est donc différent de celui présenté dans [65] qui considère les BGP à période unique. Selon [101], le problème actuel est NP-difficile et il est impossible d'obtenir une solution optimale pour les grandes instances en utilisant un solveur commercial comme CPLEX. Une approche hybride combinant un algorithme génétique et un recuit simulé (GASA) est donc proposée pour résoudre ce problème. Le GASA adopte une structure chromosomique spécifique au problème, des opérateurs de croisement et de mutation bien adaptés à la structure

	Dans ce section, un problème de génération d'enchères sur plusieurs périodes (BGP) pour un
	transporteur est pris en compte. Dans le problème, il y a deux types de demandes différentes,
	les demandes réservées du transporteur et les demandes sélectives. Le transporteur s'engage
	par contrat avec ses expéditeurs à répondre seul à toutes les demandes réservées. Les demandes
	sélectives sont proposées par d'autres transporteurs et peuvent faire l'objet d'une offre par le

concernent les demandes réservées et échangeables. Les équations (A.7) à (A.8) garantissent que toutes les demandes réservées de chaque transporteur doivent être servies par le transporteur lui-même, tandis que l'équation (A.9) implique que chaque demande échangeable peut être servie par tout transporteur. Les contraintes (A.10) et (A.11) satisfont si une demande est servie, il doit y avoir un véhicule quittant son point de ramassage et arrivant à son point de livraison jumelé. La contrainte suivante (A.12) est la contrainte de fenêtre de temps pour les noeuds de ramassage et de livraison. La contrainte (A.13) montre la faisabilité dans le temps, c'est-à-dire que le véhicule k ne peut pas commencer à desservir le noeud j avant d'avoir terminé son service au noeud i et de se déplacer du noeud i au noeud j. La contrainte (A.14) impose une restriction sur la fenêtre de temps à chaque noeud client. Les équations (A.15), (A.16) et (A.17) garantissent la durée maximale de chaque trajet, le respect de la capacité des véhicules et le nombre maximal de véhicules pour chaque transporteur. Les autres contraintes définissent les variables. A.transporteur. Chaque demande comporte une demande de ramassage et de livraison avec un point de ramassage, un point de livraison, une quantité de ramassage et de livraison et deux fenêtres de temps. chromosomique. A des fins de comparaison, nous utilisons un algorithme d'optimisation basé sur la biogéographie (BBO) qui est un algorithme basé sur la population, ses spécifications sont proches de le GA et son fonctionnement pour rechercher la meilleure solution dans une population est similaire. En comparant le GA et le BBO, chaque chromosome du GA, qui est considéré comme un individu ayant une valeur de forme physique, est un habitat dont l'indice de convenance est appelé Indice de qualité de l'Habitat (Habitat Suitability Index). Habituellement, un habitat à HSI élevé est acceptable et offre de meilleures solutions. Les résultats numériques démontrent que l'algorithme proposé peut trouver une bonne solution réalisable dans un temps de calcul raisonnable pour des cas importants.

A.

3.1 Description et modèle mathématique

  'ensemble des arcs. L'ensemble de noeuds est défini par V = {0, ..., 2n + 1}, où n représente le nombre de demandes, 0 et 2n+1 représentent le dépôt du transporteur, i et n + i représentent le point de collecte et le point de livraison de la demandes i, i = 1, 2, ..., n. Soit W l'ensemble des noeuds à exception du noeud dépôt. Comme mentionné précédemment, le problème est le BGP multi-période avec l'ensemble de périodes indiqué par H. Dans le problème, le transporteur a une flotte finie de véhicules homogènes dont l'indice est donné par K = {1, 2, ..., V K} où V K est le nombre maximum de véhicules. La capacité de chaque véhicule est indiquée par Q et la charge de chaque véhicule ne peut dépasser sa capacité. L'ensemble P = {1, 2, ..., n} est l'ensemble des noeuds de reprise de toutes les demandes et l'ensemble des noeuds de livraison est donné par D = {n + 1, ..., 2n}. Dans notre modèle, chaque demandes i a son noeud de ramassage i et son noeud de livraison i + n. La demande du noeud de ramassage de la demandes i est indiquée par d i , tandis que la demande du noeud de livraison de la même demandes est indiquée par d i+n , avec d i+n = -d i . Le noeud de livraison de chaque demande doit être visité après son noeud de ramassage sur le même itinéraire. L'ensemble de toutes les demandes est indiqué par R

	Dans ce problème, nous considérons un transporteur qui veut soumissionner à des demandes
	parmi celles ouvertes à enchère (offertes par tous les transporteurs) dans une enchère combina-
	toire afin de maximiser son propre profit en résolvant un problème de génération de soumission.
	Étant donné que le transporteur planifie ses opérations de transport à l'avance et selon un horizon
	mobile, comme il est mentionné dans l'introduction, ce problème de génération d'offres implique
	plusieurs périodes. Nous considérons le problème dans le cas du le transport de chargement
	partial, où chaque demande de transport est une demande de ramassage et de livraison avec
	fenêtres de temps, deux types de demandes, les demandes réservées et les demandes sélectives,
	sont impliquées, et chaque demande est associée à un profit qui est le revenu pour servir la
	demande. Formellement, le problème de génération d'offres multi-périodes avec les demandes

de ramassage et de livraison, les fenêtre de temps, les demandes sélectives et les demandes réservées, et les profits peuvent être définis sur un graphique dirigé G = (V , E) où V est l'ensemble des noeuds comprenant tous les noeuds de ramassage et de livraison et de dépôt du transporteur et E l

This work has been carried out within Laboratory of Industrial Systems Optimization (LOSI) at University of Technology of Troyes (UTT). It is funded by ANR (French Research Agent). pleasure to express my deep sense of thanks and gratitude to my supervisors Prof. thanks to Mme. MANIER and M.IORI for accepting review

DELIVERY, TIME WINDOWS, PROFITS, AND RESERVED REQUESTS

The name of each instance has a format n -|R r | -|R s | -source. As an example, we explain instance 10-5-5-50a. There are 10 requests in total, including 5 reserved requests (1-5) and 5 selective requests [START_REF] Bae | Multi-depot vehicle routing problem with time windows considering delivery and installation vehicles[END_REF][START_REF] Baños | A hybrid meta-heuristic for multi-objective vehicle routing problems with time windows[END_REF][START_REF] Barratt | 129 BIBLIOGRAPHY Understanding the meaning of collaboration in the supply chain[END_REF][START_REF] Chen | Mathematical model and solution approach for collaborative logistics in less than truckload (LTL) transportation[END_REF][START_REF] Boussier | An exact algorithm for team orienteering problems[END_REF]. The code 50a means this instance is derived from the original one, prob50a : Only the 10 first requests appearing in prob50a are copied in instance 10-5-5-50a. To include the period specification, we consider there are 5 periods and each period has its own reserved requests according to the random function.

In [65], for each instance size [START_REF] Boussier | An exact algorithm for team orienteering problems[END_REF][START_REF] Collette | Multiobjective optimization: principles and case studies[END_REF]30,[START_REF] Bruce L Golden | The vehicle routing problem: latest advances and new challenges[END_REF][START_REF] Al | Non-dominated ranked genetic algorithm for solving constrained multi-objective optimization problems[END_REF] or 100 requests), authors build nine instances using nine PDPTW files. These nine instances can be decomposed in three types: Three with roughly one-third of reserved requests, three with 50% of reserved requests, and three with two-thirds of reserved requests. The fleet size in [65] is adjusted in accordance with the proportion of the number of requests extracted from the original instance.

The service price of each request is set according to the coordinates of its nodes. Take request i as an example, let d i,n+i denotes the distance from its pickup node i to delivery node n + i, then this request is given a service price p i = d i,n+i .λ, λ ∈ [START_REF] Al Jadaan | Parametric study to enhance genetic algorithm performance, using ranked based roulette wheel selection method[END_REF][START_REF] Archetti | Multi-period Vehicle Routing Problem with Due dates[END_REF]. This formula generates a large proportion of profitable requests and a small proportion of non-profitable requests [65].

The instances are executed in CPLEX12.6 on a laptop with an Intel core i5 CPU and 4.00 GB RAM. Note that for the medium instances and large instances, it is impossible to solve the MILP model optimally by CPLEX after 2 hours and 4 hours of running time, respectively.

Parameter setting

The performance of GASA algorithm and BBO algorithm depends on the quality of their parameters setting. The values of some parameters of the two algorithms are determined empirically and are given in Table 4. [START_REF] Archetti | Multi-period Vehicle Routing Problem with Due dates[END_REF]. The values of their other parameters are tuned by using Taguchi method, which is a popular and efficient parameter tuning technique based on fractional experiments (FFE) [START_REF] Semioshkina | An overview on taguchi method[END_REF]. The parameters of the two algorithms selected to tune are in Table 4. [START_REF] Bae | Multi-depot vehicle routing problem with time windows considering delivery and installation vehicles[END_REF], and their values are given in Table 4.7 and Table 4.

Parameter Description Value

SubIt

Number of iteration of SA 110 µ m

Mutation rate 0.26

Test results and optimality gaps

After the parameter calibration, we execute GASA algorithm, BBO algorithm and CPLEX on all instances. Since both GASA and BBO algorithms contain random factors to reduce the impacts

Criterion Description

Gap M ILP

The relative gap between LB M ILP and UB M ILP , defined as

Gap BBO

The relative gap between UB M ILP and Ob j BBO , defined as

The relative gap between LB M ILP and Ob j G AS A , defined as

an optimal solution. However, for some of small instances with 8 requests and most medium to large size instances, CPLEX could not even find a feasible solution in a preset computation time, whereas both algorithms could find a feasible solution for all instances. Actually, for most instances with the number of requests more than 8, no feasible solution is obtained by CPLEX, so we compare the solutions obtained by our two algorithms based on their relative gaps with the upper bound obtained by CPLEX, i.e., using the above-mentioned criteria. The applied algorithms can find an optimal solution for all small instances with 6 requests. They can find a solution with the relative profit gap smaller than 0.34% for 8 requests instances and can find a solution with the relative profit gap smaller than 4.50% for 10 requests instances. For medium instances, our GASA algorithm can find a solution with the gap smaller than 5.6%, whereas our BBO algorithm can find a solution with the gap smaller than 6.117%. For instances with 30 requests, GASA algorithm can find a solution with the gap smaller than 6.98%, while our BBO algorithm can find a solution with the gap smaller than 7.74%. For instances with 30 requests, our GASA algorithm can find a solution with the gap smaller than 10.31%, whereas our BBO algorithm can find a solution with the gap smaller than 11.60%. For instances with 50 requests, our GASA algorithm can find a solution with the gap smaller than 13.2%, whereas our BBO algorithm can find a solution with the gap smaller than 13.6%. In the instances with 100 requests, our GASA algorithm can find a solution with the gap smaller than 16.4% and BBO algorithm can find a solution with the gap smaller than 18.2%. Moreover, our proposed algorithms are much better than CPLEX, Table 4.12, in terms of running time for medium and large instances, although the running time of the two proposed algorithms increases naturally with the size of instance and the computation time of CPLEX is smaller than those of the algorithms for small instances with 6 requests. To compare the two algorithms we utilize RPD that has been mentioned in the previous chapter. After calculating RPD, statistical analysis is done as we mentioned in Chapter 3. According to Table 4.13, Table 4.14, and Fig. 4.5, H 0 is rejected. GASA has better profit, small RPD, and running time smaller than those of BBO respectively for all instances; therefore GASA two ways to evaluate each bid from carriers. The first approach is a weighted score method, that is, we assign a weight to each attribute (cost and delivery lead time) of a bid and then transform two attributes into a single score. It means that evaluating a bid is according to a score function combining cost and delivery lead time, as in the multi-attributes score auction [START_REF] Ghosh | Scoring auctions: A brief survey[END_REF]. The other method is a bi-objective method which is treated with all attributes (objectives) separately without transforming them into a single score function. In this approach, a bid is evaluated based on its both attributes (cost and delivery lead time) as two different objective functions.

To solve the problem, we present mathematical programming models to both cases. For the single objective multi-period BGP with pickup and delivery requests, time windows, profits, and delivery lead time, we apply GASA and ITS. After that, we compare two algorithms with CPLEX.

To solve bi-objective multi-period BGP, two well-known multi-objective algorithms, NSGA-II and NRG are presented. NSGA-II and NRGA algorithms are compared based on standard metrics.

Literature review

This section is devoted to review articles related to bi-objective multi-period bid generation problem with pickup and delivery requests, time windows, profits, and reserved requests. In Chapter 3 and Chapter 4, the previous works related to collaborative transportation planning with pickup and delivery requests and multi-period bid generation problem have been analyzed.

In this section, the works related to the transportation service with the consideration of delivery lead time are studied.

In [38] authors express the impact of collaborative transportation on transportation lead-time through empirically investigating on. In [START_REF] Hu | Transportation service procurement problem with transit time[END_REF] a bi-objective integer programming model is proposed to formulate the problem. The authors find that many shippers take attention to have short transit time besides costs minimization. A bi-objective branch-and-bound algorithm that finds all non-dominated solutions is developed to solve the problem. Mathematical expressions for the transit time of cargo is presented in [29]. The authors propose two new trans-shipment policies:

Backward trans-shipment and one-to-many trans-shipment, and mathematically calculate the corresponding connection times. Similar problems also are found in passengers transportation.

In [START_REF] Cevallos | Minimizing transfer times in public transit network with genetic algorithm[END_REF], a genetic algorithm is used to the optimization of transfer times in a bus transit system.

The algorithm for this transfer time optimization problem tries to find the best feasible solution by shifting existing timetables.

As the problem presented in this chapter is close to multi-objective vehicle routing problems, a few works on multi-objective vehicle routing problems are cited. In [START_REF] Baños | A hybrid meta-heuristic for multi-objective vehicle routing problems with time windows[END_REF] the authors consider two objective functions for a vehicle routing problem with time windows: The minimization of costs and the minimization of workload imbalance in terms of distances traveled by the vehicles.

The suggested algorithm to solve the problem is a Pareto-based hybrid algorithm that integrates evolutionary computation and simulated annealing. In addition to the minimization of total Weight of delivery lead time for request i.

Problem description and mathematical model

Our considered problem in this chapter is a transportation-planning problem with pickup and delivery requests, hard time windows defined on a directed graph G = (V , E), where V is the set of all nodes and E is the set of edges with the following specifications. Each request i is associated Temps de déplacement du noeud i au noeud j, il est supposé égal au coût de déplacement du noeud i au noeud j. T Durée de chaque route. BM i, j = l j -e i Utilisé dans les contraintes de fenêtres de temps.

Utilisé dans les contraintes de capacité des véhicules. j∈P; j =i

j∈V , j =i,m

j∈V , j =i,m

x j(i+n)km = y ikm ∀i ∈ P, k ∈ K m , ∀m ∈ M (A.11)

x jikm ≤ K m ∀i ∈ M, ∀m ∈ M (A.18)

A.3. PROBLÈME DE GÉNÉRATION D'ENCHÈRES SUR PLUSIEURS PÉRIODES AVEC DEMANDES DE RAMASSAGE ET DE LIVRAISON, PROFITS ET DEMANDES RÉSERVÉES

j∈V , j =i,0

x j(n+i)kh = y ikh ∀i ∈ P, k ∈ K, ∀h ∈ H (A.28)

j∈V , j =i,2n+1

x j(i+n)kh = y ikh ∀i ∈ P, k ∈ K, ∀h ∈ H (A.29)

A.4 Problème de génération d'enchères sur plusieurs périodes avec prise en compte des délais de livraison

Dans les entreprises, en plus de minimiser tous les coûts, l'expéditeur est interessé par la réduction du délai de livraison. La réduction les délais de livraison présente deux avantages.

Dans un premier temps, des délais de livraison plus courts rendent agile la gestion de la chaîne d'approvisionnement et la réponse aux commandes est exécutée plus rapidement. Ainsi, elle Fenêtres de temps du point de livraison du point de ramassage i.

Fenêtre de période de la demande sélective i. t i j Temps de déplacement entre deux noeuds i et j. c i j cout de déplacement entre le noeud i et j i and j. T Durée maximale de chaque route. BM i j = l j -e i Formuler linéairement les contraintes de fenêtre temporelle si l j est la limite supérieure de la fenêtre de temps pour le noeud j et e i est la limite inférieure de la fenêtre de temps pour le noeud i. x j(i+n)kh = y ikh ∀i ∈ P, k ∈ K, ∀h ∈ H (A.46)

) and y ikh = 0 pour tout i ∈ R rl,l =h (A.56) [30] Ozlem Ergun, Gultekin Kuyzu, and Martin Savelsbergh.

The lane covering problem.

Manuscript, 2003.

[31] Ozlem Ergun, Gultekin Kuyzu, and Martin Savelsbergh.

Reducing truckload transportation costs through collaboration.

Transportation science, 41(2):206-221, 2007.

[32] Özlem Ergun, Gültekin Kuyzu, and Martin Savelsbergh.

Shipper collaboration.

Computers & Operations Research, 34(6):1551-1560, 2007.

[33] Terry L Esper and Lisa R Williams.

The value of collaborative transportation management (ctm): its relationship to cpfr and information technology.

Transportation journal, pages 55-65, 2003.

[34] Dominique Feillet, Pierre Dejax, and Michel Gendreau.

Traveling Salesman Problems with Profits.

Transportation Science, 39(2):188-205, 2005.

[35] Margaretha Gansterer, Murat Küçüktepe, and Richard F. Hartl.

The multi-vehicle profitable pickup and delivery problem.

OR Spectrum, 39(1):303-319, 2017.

[36] Abel Garcia-Najera and John A Bullinaria.

An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows.

Computers & Operations Research, 38(1):287-300, 2011.

[37] M Gendreau, G Laporte, and F Semet.

A tabu search heuristic for the undirected selective traveling salesman problem.

European Journal of Operational Research, 106(2):539-545, 1998.

[38] Hadi Ghaderi, Wout Dullaert, and Walther Ploos Van Amstel.

Reducing lead-times and lead-time variance in cooperative distribution networks. [58] Vijay Krishna.

Auction theory.

Academic press, 2009.

[59] Roy H Kwon, Chi-Guhn Lee, and Zhong Ma.

An integrated combinatorial auction mechanism for truckload transportation procurement. [64] Jian Li and Wenhua Lu.

Full truckload vehicle routing problem with profits.

Journal of Traffic and Transportation Engineering (English Edition), 1(2):146-152, 2014.

[65] Yuan Li, Haoxun Chen, and Christian Prins.

Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved requests.

European Journal of Operational Research, 252(1):27-38, 2016.

[66] Ran Liu, Zhibin Jiang, Richard YK Fung, Feng Chen, and Xiao Liu.

Two-phase heuristic algorithms for full truckloads multi-depot capacitated vehicle routing problem in carrier collaboration.

Computers & Operations Research, 37(5):950-959, 2010.

[67] S Afshin Mansouri.

A multi-objective genetic algorithm for mixed-model sequencing on jit assembly lines.

European Journal of Operational Research, 167(3):696-716, 2005.

[68] Evangelos Markakis and Amin Saberi.

On the core of the multicommodity flow game.

Decision support systems, 39(1):3-10, 2005.

[69] Robert Mason, Chandra Lalwani, and Roger Boughton.

Combining vertical and horizontal collaboration for transport optimisation.

Supply Chain Management: An International Journal, 12(3):187-199, 2007.

[70] Hadi Moradi, M Zandieh, and Iraj Mahdavi.

Non-dominated ranked genetic algorithm for a multi-objective mixed-model assembly line sequencing problem.

International Journal of Production Research, 49(12):3479-3499, 2011.

[71] Seyed Mohsen Mousavi, Seyed Taghi Akhavan Niaki, Esmaeil Mehdizadeh, and Mohammad Reza Tavarroth.

The capacitated multi-facility location-allocation problem with probabilistic customer location and demand: two hybrid meta-heuristic algorithms.

International Journal of Systems Science, 44(10):1897-1912, 2013.

[72] Seyed Mohsen Mousavi, Javad Sadeghi, Seyed Taghi Akhavan Niaki, and Madjid Tavana.

A bi-objective inventory optimization model under inflation and discount using tuned pareto-based algorithms: Nsga-ii, nrga, and mopso.

Applied Soft Computing, 43:57-72, 2016.

[73] Amir Abbas Najafi, Seyed Taghi Akhavan Niaki, and Moslem Shahsavar.

A parameter-tuned genetic algorithm for the resource investment problem with discounted cash flows and generalized precedence relations.

Computers & Operations Research, 36(11):2994-3001, 2009.

[74] Viet Hung Nguyen and Thi Thu Thuy Nguyen.

Approximating the asymmetric profitable tour.

Electronic Notes in Discrete Mathematics, 36(C):907-914, 2010.

[75] Daichi Niizuma, Keiichiro Yasuda, and Atsushi Ishigame.

Multipoint tabu search based on proximate optimality principle-application of parts concept. [94] R Tavakkoli-Moghaddam, A Makui, and Z Mazloomi.

IEEJ Transactions on

A new integrated mathematical model for a bi-objective multi-depot location-routing problem solved by a multi-objective scatter search algorithm.

Journal of Manufacturing Systems, 29(2-3):111-119, 2010.