The fleet size and mix vehicle routing problem with pickups and deliveries

(1)

Master’s degree thesis

LOG950 Logistics

The Fleet Size and Mix Vehicle Routing Problem with Pickups and Deliveries

Gurpiar Singh Cheema

Number of pages including this page: 55

Molde, 23 May 2016

(2)

Mandatory statement

Each student is responsible for complying with rules and regulations that relate to examinations and to academic work in general. The purpose of the mandatory statement is to make students aware of their responsibility and the consequences of cheating. Failure to complete the statement does not excuse students from their responsibility.

Please complete the mandatory statement by placing a mark in each box for statements 1-6 below.

1. I/we hereby declare that my/our paper/assignment is my/our own work, and that I/we have not used other sources or received other help than mentioned in the paper/assignment.

2. I/we hereby declare that this paper

1. Has not been used in any other exam at another department/university/university college

2. Is not referring to the work of others without acknowledgement

3. Is not referring to my/our previous work without acknowledgement

4. Has acknowledged all sources of literature in the text and in the list of references

5. Is not a copy, duplicate or transcript of other work

Mark each box:

1.

2.

3.

4.

5.

3.

I am/we are aware that any breach of the above will be considered as cheating, and may result in annulment of the examination and exclusion from all universities and university colleges in Norway for up to one year, according to the Act relating to Norwegian Universities and University Colleges, section 4-7 and 4-8 and Examination regulations section 14 and 15.

4. I am/we are aware that all papers/assignments may be checked for plagiarism by a software assisted plagiarism check

5. I am/we are aware that Molde University College will handle all

cases of suspected cheating according to prevailing guidelines.

6. I/we are aware of the University College’s rules and regulation for

using sources

(3)

Publication agreement

ECTS credits: 30

Supervisor: Arild Hoff

Agreement on electronic publication of master thesis

Author(s) have copyright to the thesis, including the exclusive right to publish the document (The Copyright Act §2).

All theses fulfilling the requirements will be registered and published in Brage HiM, with the approval of the author(s).

Theses with a confidentiality agreement will not be published.

I/we hereby give Molde University College the right to, free of

charge, make the thesis available for electronic publication: yes no

Is there an agreement of confidentiality? yes no

(A supplementary confidentiality agreement must be filled in)

- If yes: Can the thesis be online published when the

period of confidentiality is expired? yes no

Date: 23-May-16

(4)

Preface and Acknowledgement

This master thesis is written as a necessary work to obtain MSc degree in Logistics at Molde University College -Specialized University in Logistics. The dissertation work has been carried out from December 2015 to May 2016. Associate Professor Arild Hoff supervised the thesis work. Also, discussions with Professor Lars Magnus Hvattum turned out to be fruitful in association with the thesis work.

I would be grateful to pay my gratitude to my supervisor Associate Professor Arild Hoff for his sincere guidance towards my work and the valuable opinions given in the context of the thesis. I am heartily thankful to Professor Lars Magnus Hvattum also for his help.

I would also say thanks to the academic staff and the officials at Molde University College for giving me the opportunity to explore a new academic environment and the social life here in Norway.

Gurpiar Singh Cheema Molde, Norway

May 2016

(5)

Summary

This master degree thesis introduces a new dimension to the Fleet Size and Mix Vehicle Routing by adding Simultaneous Pickups and Deliveries (FSMVRPPD) at the customers. A literature study has been conducted to investigate the previous work on the particular problem. The idea to explore this particular problem has come from the transportation structure of two different local industries. Although, these have no direct or indirect association with this thesis. A mathematical model has been presented to define the problem in full. This particular problem has the nature of combinatorial optimization and combines two NP-hard problems. Therefore, an Iterated Local Search algorithm has been proposed to investigate results conducted on the standard benchmark instances for the Fleet Size and Mix problems. These benchmark instances were modified to fit with the FSMVRPPD. An analysis of the outcomes from the ILS algorithm was conducted to see the change in the objective value and the structure of the solution. The investigation also led to observe the how challenging the results are from the ILS approach.

(6)

List of Figures

Figure 1. Classification of Pickup and Delivery problem (ref. Lin et al. 2014) ... 6

Figure 2 Clark and Wright Savings Algorithm (Ref. Clarke and Wright (1964) ... 12

Figure 3 A VRP problem scenario ... 18

Figure 4 Vehicle routing solution to example ... 19

Figure 5 General Procedure for Iterated Local Search... 23

Figure 6 Probability densities of costs ... 24

Figure 7 ILS procedure ... 25

Figure 8 Initialization procedure ... 27

Figure 9 Procedure for creating a random solution ... 27

Figure 10 procedure for adjusting the vehicle to the best fitted for meeting the customer demand on the route ... 28

Figure 11 Procedure for checking whether a solution is feasible or not ... 29

Figure 12 Procedure for calculating the total cost of a solution ... 29

Figure 13 Local Search procedure ... 32

Figure 14 Procedure for optimizing single routes using the 2-opt neighbourhood... 34

(8)

List of Tables

Table 1 AMPL results for the FSMVRPPD ... 36

Table 2 Results from the ILS solver for the FSMVRPPD ... 38

Table 3 Comparison of results from the FSMVRP literature ... 39

Table 4 The benchmark instances from (Golden et al. 1984) ... 47

(9)

1.0 Introduction

In the present market, the oil price crises put many companies to revise their transportation costs to be stable in the business. The transportation costs should require the attention of management as it, in general, is considered to account for about 20% of the total cost of a product (Hoff et al. 2010). Emergent economy, mounting consumption, and globalization give an increasing focus on transport solutions. Fierce competition between transporters and producers results in efficiency, better end-user service, on-time delivery and of course the need to cut off the transportation cost. By now, there are several tools, methods, models and software available in the market for improving transport efficiency and reducing the transportation costs, also by considering other aspects of better service such as on-time delivery, customer service, quality service etc.

A very central issue when improving the transport efficiency is finding the optimal way of visiting customers described as the Vehicle Routing Problem (VRP). The general VRP was first defined by (Dantzig and Ramser 1959) as the problem of minimizing the costs of routing a fleet of vehicles to serve a set of customers with a given demand. The demand could be either pickup or delivery of goods, and the vehicles were assumed to have a fixed and homogeneous capacity. Later, several extensions of the VRP is described in the research literature, but real-world problems are in general complex and contains different constraints and requirements which make the standard models insufficient.

In this thesis, we are going to discuss a more realistic aspect of transportation by combining two of the earlier defined extensions of the VRP. The thesis is focusing on selecting a fleet of different vehicles and creating routes where the demand of several customers is going to be fulfilled. The customers can have both a pickup and delivery demand at the same time, which makes it necessary to check the vehicle capacity at any point during the routes. We call this problem the Fleet Size and Mix Vehicle Routing Problem with Pickups and Deliveries (FSMVRPPD), which can be seen as a combination of two earlier defined variants of the VRP. These are the Fleet Size and Mix VRP (FSMVRP) described by (Gheysens, Golden, and Assad 1984) and VRP with Pickup and Delivery (VRPPD) described by (Alfredo Tang Montané and Galvão 2006).

The problem is related to the design of distribution networks for businesses. The

(10)

distribution networks require a significant share of investment; therefore, it is a precarious issue for many companies.

The motivation to study this problem comes in particular from by looking at the general transportation of two local businesses. One is a bakery, and another is a cold drink factory both located in the town of Molde. The bakery distributes products to a smaller region as compared to the cold drinks factory. They both have a diversified fleet of vehicles but in limited numbers. Both of them deliver their products in plastic crates and then collect these containers (empty or sometimes with returned products) from the customers. Depots are located at the same location as the production factory. These aspects in the VRP terminology are described as heterogeneous vehicle fleet, single supply station or distribution center and customers with two types of demand, i.e. Pickup and Delivery, simultaneously. Study of the previous literature revealed that the FSMVRPPD has not been studied significantly in the research literature. The examples mentioned above are two specific situations from the real world industries that are relatively close to the FSMVRPPD. But the FSMVRPPD could be actual for a load of similar companies and also in other variants of industries.

In this thesis, we are going to make decisions on the selection of an appropriate vehicle fleet from the available alternative vehicle types. Also, as this transportation network is going to serve the customers, finding optimal routes with the chosen vehicle fleet is a priority. The demand of the customers is the main focus in this problem solution. Each customer has some delivery demand or some pickup demand or both.

The first aspect of the problem is to choose the best suitable vehicle fleet. A homogeneous vehicle fleet can do the job in more general cases. However, this is usually not the case for real industrialized problems, where adopting a fleet of similar vehicles would not be cost efficient. Therefore, the inclusion of heterogeneous vehicles in the fleet would be more profitable and reflect the real industrialized problems. It is also a fact that the vehicles usually are acquired over a long period; thus, mechanical and technological developments in that time period leads to vehicles of different features and properties. There are three main categories to differentiate aspects of vehicle types (Hoff et al. 2010):

(11)

 Physical Dimensions

 Compatibility Constraints

 Costs of Operation

Physical characteristics of a vehicle put constraints on the capacity of the vehicle. Not only the physical appearance affects the capacity, but some technical issues also control the load capacity. The speed of a vehicle can also be identified as a physical restriction.

Compatibility constraints deal with the different types of commodities to be loaded on the vehicles. Compatibility issues concern most when commodities of the different state are going to be shipped, such as Liquids, Gasses and Solid materials. Solid materials are most compatible to transport while liquids and gasses call for some special kind of tanks and chambers to fill in. Another issue is to deal with items those strictly need different storage environment such as cold storage, pressure tanks, vacuum, etc. The food items which require freezer trucks while transportation is the typical example of this constraint.

The operational cost of the vehicles is also an important factor when selecting the fleet. As all efforts of operational research and decision support systems are to come up with a cost-efficient and profit oriented solution. Costs include the acquisition cost, depreciation cost, maintenance cost, and environmental cost.

In this thesis, we have considered the two primary aspects of heterogeneous vehicles, which is deemed to be the loading capacity and the operational cost of vehicles.

In this thesis, a mathematical model is formulated to describe the problem. Smaller instances are solved to optimality by using the exact mathematical model, and a metaheuristic is developed to solve larger instances of the problem. I chose to use a variant of the metaheuristic Iterated Local Search to solve the large problem instances as mentioned by (Subramanian et al. 2012) and (Lourenço, Martin, and Stützle 2010). Results from both the exact method and the metaheuristic are achieved and compared to the solution of

(12)

standard instances for the FSMVRP to see how the pickup and delivery constraints affect the objective value and composition of fleet and routes.

In the next chapter, a discussion on the background of FSMVRPPD has been written, which also includes a review of various related papers. The FSMVRPPD is described in Chapter 3. In Chapter 4, we present the mathematical model following by the Iterated Local Search metaheuristic in Chapter 5. Chapter 6 will cover the computations, interpretation, and comparison of results using the methods described in Chapters 4 and 5. At last, a conclusion will be presented in Chapter 7 in combination with suggestions for further research on the problem.

2.0 Problem Background and Literature study

In this chapter, we will discuss the history of routing problems thoroughly, starting from the first time when this problem was introduced. It means that we are going to address the problem from its basis until the current situation. The focus of this thesis is to define the problem as well as possible. Therefore, a classification scheme of previous VRP work concentrates on the nature, characteristics and application scenarios of the problems.

2.1 VRP

Vehicle Routing Problems are concerned with the delivery of some commodities from one or more depots to a number of customer locations with known demand. Such problems arise in many physical systems dealing with distribution networks. For example, delivery of commodities such as mail, food, newspapers, etc. The specific problem which arises is dependent upon the type of constraints and management objective. This definition is given by (Achuthan, Caccetta, and Hill 1997).

(Lin et al. 2014) Categorized the following extensions to VRP in their survey on Green Vehicle Routing Problem. They have reviewed the last 50 years of VRP, which enlightens the way to study the history of VRP and its extensions and to define the current problem presented in this thesis.

(13)

2.2 Extensions to VRP

i. Capacitated VRP (CVRP)

(Dantzig and Ramser 1959) First introduced the vehicle routing problem by describing a real world problem of gasoline delivery to a large number of small- sized service stations from a big size distribution terminal. As we know, when we have a large number of customers to be served, the number of possible routes are also increased exponentially. This results in difficulties in finding the optimal routing for the problem. They developed an algorithm approach based on a linear mathematical formulation to produce a near to the optimal solution to the problem. In their problem, the delivery trucks had a loading capacity which makes the problem a Capacitated VRP. By analyzing the cost matrix for the travel distances, the CVRP can be categorized into Symmetric CVRP and Asymmetric CVRP depending on the distance between two nodes are the same independent of direction or not (Toth and Vigo 2002), they used the branch and bound algorithms to solve the problems.

ii. Time-dependant VRP (TDVRP)

In this type of vehicle routing problem, the real world traffic effects the traveling time of the vehicles in between various nodes. The increase in traffic density can reduce the vehicle speed and travel time would be increased. Traditionally, in the VRP, Euclidean distances between nodes are predicted as constant, but this is usually not the situation in a real world case. As a consequence, the actual traveling cost can be calculated completely wrong (Polimeni and Vitetta 2013).

A method to generate travel times based on the area or location of the vehicle and on the time of day is proposed by (Lecluyse, Sörensen, and Peremans 2013).

They found out that previous work was not good enough to generate time- dependent travel times. The method proposed by them is able to create travel time profiles for all the edges in a traveling network where congestion areas can be defined by users. Also (Cooke and Halsey 1966) stated that the constant traveling time between two nodes (vertices) is not true for many real world applications. Therefore, they proposed an iteration scheme to find the shortest

(14)

path by considering variable travel times between nodes. Another extension to Time-dependant VRP is discussed by (Solomon 1987) as VRP with scheduling and Time Windows constraints. (Figliozzi 2012) solve the time dependent problems with hard time windows. The proposed algorithm can handle both constant and variable speed as well as hard and soft time windows.

iii. Pickup and Delivery VRP (VRPPD)

There is a huge collection of research papers available on pickup and delivery problems. (Lin et al. 2014) presented a classification of these type of problems, which can be seen in

Figure 1. They referred this classification from (Parragh, Doerner, and Hartl 2008a, b). The first time pickup and delivery problems were described by (Wilson and Weissberg 1967)as a dial-a-ride problem.

Figure 1. Classification of Pickup and Delivery problem (ref. Lin et al. 2014)

Transportation from/to depot. There are four specific problems specified when transporting goods from or to a depot.

(a.) VRP with Clustered Backhauls (VRPCB) states that the group or cluster of linehaul (delivery) customers should be served before starting to visit backhaul (pickup) customers.

In VRPCB, the customers can have either delivery demand or pickup demand, but not both.

(b.) VRP with Mixed Linehauls and Backhauls (VRPMLB) allow mixed visits to customers. This means vehicles are allowed to visit customers in any sequence, but in one visit only one of the operation performed that could be either delivery or pickup.

(c.) VRP with Divisible Delivery and Pickup (VRPDDP) some customers are visited first for only delivering the goods without any pickup. After that, the remaining customers are

(15)

visited to perform both delivery and pickup operation. On the way back, before the vehicle return to the depot, the remaining pickups, which were left at the start of the route are processed.

(d.) VRP with Simultaneous Delivery and Pickup (VRPSDP). Both the delivery and pickup operations must be performed in a single visit to each customer. VRPSDP is the variant considered in the FSMVRPPD.

Transportation between Customers is classified into three problems.

(a.) Pickup and Delivery VRP (PDVRP). A vehicle traverses across a route to transport the goods, which consists of unpaired pickup and delivery points. Here it is assumed that every unit picked up can be used to satisfy every delivery customer’s demand (Parragh, Doerner, and Hartl 2008a).

(b.) Classical Pickup and Delivery problem (PDP) this problem can be simplified by considering the example of a bus. A bus driver picks up passengers from different locations and transport them to other locations, where, the driver could have another pickup or not.

Means there is no central location/depot of goods. They are distributed over the network of nodes.

(c.) Dial-a-Ride Problem (DARP) points to routing and scheduling of vehicles to fulfil the pickup and delivery requests of customers between the start and end point of travel (Cordeau and Laporte 2007). Problems of this kind arise, e.g., in connection with the transportation of handicapped or elderly persons. Another possible application is, the transportation of perishable goods, that also requires maximum ride time limits (Parragh, Doerner, and Hartl 2008a).

iv. Fleet Size and Mix VRP (FSMVRP)

Fleet Size and Mix VRP (FSMVRP) is a situation where one has to decide the fleet composition from the available vehicle fleet and routing of the vehicles simultaneously (Golden et al. 1984). (Baldacci, Battarra, and Vigo 2009) have solved FMSVRP based on two-commodity network flow by proposing a mixed integer programming formulation. (Liu, Huang, and Ma 2009) proposed a genetic algorithm based heuristic to FSMVRP with and without fixed cost. They demonstrate that genetic algorithm approach is as competitive as other, a mathematical programming based and local search based approaches. The FSMVRP with Time Windows has been deeply studied over the past decade.

(16)

Some recent studies on FSMVRPTW are done by (Repoussis and Tarantilis 2010) and (Belfiore and Yoshizaki 2013).

v. Multi-depot VRP (MDVRP)

MDVRP is an extension to the CVRP by introducing more than one depot location. Every customer is visited by a vehicle assigned to one of the depots.

Origin and destination for a vehicle route must be same depot (Lin et al. 2014).

vi. Stochastic VRP

When one or more components in the VRP are uncertain. SVRP can contain stochastic customers, where probability determines the presence of the customer or not, or the problem can have stochastic demand. Service time and travel time could also be random variables (NEO 2013).

vii. Location Routing Problem (LRP)

Two main decisions have to be taken; one is to select the appropriate depot location and another one is to construct the routes to service the customers. A half century ago (Boventer 1961) introduced the idea of combining location and routing decisions, later, as more rich research known as Location Routing Problem (LRP). Most recent search can be observed from the articles (Koç et al.

2016), (Prodhon and Prins 2014).

viii. Periodic VRP (PVRP)

The objective of PVRP is to find feasible routes such that total routing cost during the time horizon could be minimized. Other important aspects in PVRP are that customers do not need to be visited in every period and the routes can be different in various periods. (Beltrami and Bodin 1974) has proposed algorithms to solve out the municipal waste collection routing problem. They consider time constraint, where locations of waste require a different number of visits and also different combinations of days in a week for a visit. Many real-world situations, such as waste collection, industrial gas distribution, grocery industry and picking up raw materials from suppliers (Alegre, Laguna, and Pacheco 2007), has inspired to study PVRP significantly.

(17)

ix. Dynamic VRP

The situation in real world VRP problems is not always constant or static. Over the time, conditions could be different because of uncertainty such as vehicle breakdown, continually getting customer’s orders, traffic control etc. (Lin et al.

2014). In a dynamic VRP, the routes can be changed while executed due to such unplanned situations.

x. Inventory Routing Problem

The products are transported from supplier to customer to fulfil the customer’s demand over a time period. The customer’s demand is deterministic and the time period can be finite or infinite. Transportation is done by a fleet of capacitated vehicles. The inventory cost is applied to customers as well as the supplier. The purpose is to minimize the total routing cost including inventory cost by dealing with time horizon constraint (Bertazzi and Speranza 2012). Typical for these type of problems is that they are not driven by customer orders, but by the customers size of inventory. Thus, it is the supplier who has to make sure that the customers are resupplied before they get out of stock.

xi. Split delivery VRP (SDVRP)

In SDVRP, a fleet of homogeneous vehicles serve the customers, but different from the classical VRP the customers can be visited more than once. This situation occurs where customers may have larger demand than the capacity of the vehicle but not necessarily. Each vehicle must have the same depot as starting and ending point (Archetti and Speranza 2008). The SDVRP was first introduced by (Dror and Trudeau 1989). They showed that one could have savings in cost by splitting the deliveries. (Archetti, Savelsbergh, and Grazia Speranza 2008) wrote in their paper that savings depend on the features of the instance. They found that it could be more beneficial if the average customer demand is slightly more than the half of the vehicle capacity and the variance in customer demand is small.

2.3 Solution methods

From the study of literature available in the previous section, it is clear that the standard VRP is a combinatorial optimization type and therefore NP-hard as described by

(18)

(Stutzle 1998). The FSMVRPPD combines two variants i.e. VRPPD and FSMVRP which makes the problem even harder. Thus, developing a good solution method is not an easy process. There are numerous papers pointing to various approaches to follow while finding the best solution for these types of problems. In general, the vehicle routing problems can be handled through two main classes of solution methods as shown below:

(i) Exact Methods

(ii) Approximation Methods

 Heuristics

 Meta-heuristics

2.3.1 Exact Methods

Finding the exact optimal solution by using some mathematical techniques know as exact methods. In exact methods, there are some functions which follow the mathematical rules for calculations to develop the solutions. For limited size instances, an exact simple method could be to enumerate all possible solutions fully.

But, using such type of methods is in practice infeasible for larger instances due to the exponential size of the solution space. The best known exact method for optimization problems is the Branch and Bound algorithm (Stutzle 1998).

Researchers have always been challenged to solve NP-hard optimization problems to optimality since computers can be used to solve these problems. Noteworthy progress has been made for solving these problems in recent time span, but still only smaller instances can be solved. Vehicle routing problems belong to a class of problems that has proved to be difficult to solve. Only moderately sized problems can be solved to optimality consistently (Ropke 2005). FSMVRPPD is a combinatorial optimization problem that combines the aspects of two other combinatorial problems. Therefore, we cannot expect an instant optimal solution for large or moderate instances of this problem.

Three main classes of exact methods for VRP are proposed by (Toth and Vigo 2002); Branch and Bound, Branch and Cut and Set Covering based algorithm.

Branch and Bound Algorithms are based on the idea of divide and conquer.

A large solution space is divided into smaller subproblems for solving them

(19)

separately. A lower bound is found by a linear relaxation of the original problem to determine whether to continue the decomposition of the problem or if optimal solution which satisfies all the constraints, has been reached.

(Laporte and Nobert 1987) has done a detailed study on the branch and bound algorithm.

Branch and Cut Algorithms are likely to branch and bound algorithm but use a cutting plane algorithm to get linear constraints which are satisfied by all feasible integer values, but excludes present fractional solutions. The inequalities added to the problem yields a less fractional solution. The problem then divided in two and solved again. This process is repeated until a solution satisfying all the integer constraints is found.

Set Covering based algorithms are based on the enumeration technique, where all feasible routes in the problem are enumerated and the best possible solution set covering all the customers is selected. Enumeration is a time- consuming process and even enumerating a small instance is not easy. The column generation heuristic can overcome this problem by enumerating only a small subset as the possible routes. In Column Generation, the idea is to generate only those routes which have the potential to decrease the total cost.

Firstly, a master problem (original problem) is solved to obtain the value for each constraint. A negative reduced cost is obtained from the subproblem which is obtained from the master problem. Then the negative reduced cost is added to the master problem and the master problem is resolved. This process is repeated until the subproblem generates no negative cost. Each column represents a feasible route for a vehicle and the set of routes covering all customers exactly once represent a feasible solution.

2.3.2 Heuristics

Solving large combinatorial optimization problems by using exact methods is not easy. So heuristics are commonly used as rules of thumb to solve large instances on these type of problems and produce good solutions in short time.

Heuristics can be categorized as:

 Constructive heuristics

 Improvement heuristics

(20)

A constructive heuristic is initialized by building the solution from a fresh starting point and adding the most acceptable components step by step until a full solution is constructed. The most famous constructive heuristics are the Sweep algorithm and Clarke and Wright Savings algorithm.

In the Sweep Algorithm, a straight line is imagined from the starting point (depot) of a route and then, it is swept across the area around the origin point. The sweeping could be clockwise or anti-clockwise. Nodes are added to the route due to the angle of the sweeping line, and when the capacity of a vehicle is reached a new vehicle is introduced

In Clarke and Wright Savings Algorithm (Clarke and Wright 1964), the idea is to obtain maximum cost savings by combining two routes into a single route as shown in Figure 2.

Figure 2 Clark and Wright Savings Algorithm (Ref. Clarke and Wright (1964)

In Figure 2(a) two separate routes for nodes i and j are shown. But i and j can be visited in single route as shown in Figure 2(b). To combine two routes into one route, the cost savings is calculated for nodes included in the routes. The formula to calculate the savings is:

𝑆 = 𝑐_𝑖,0+ 𝑐_0,𝑗− 𝑐_𝑖,𝑗

Where, c denotes the cost of traveling to related nodes in the routes.

An improvement heuristic focuses on to improve an existing solution by applying changes within a vehicle route or in between different vehicle routes. These changes or modifications could be moving a customer to another route, exchange customers between two routes, change in the visiting sequence in one route, etc. A Local Search implements the modifications to one local solution in expectation of

(21)

finding improved solution. The Local Search will stop if no improvement solution is found. The Local Search relies on the definition of a neighbourhood which is the possible new solutions that can be reached from a solution by performing one move.

Then the resulting solution is defined as a local optimum.

2.3.3 Metaheuristics

The idea is to combine two or more heuristics to generate high-quality solutions. The term metaheuristic was introduced by Fred Glover in 1986 and is defined by (Glover and Kochenberger 2003) as:

“ Metaheuristics, in their original definition, are the solution methods that orchestrate an interaction between local improvement procedures and higher level strategies to create a process capable of escaping from local optima and performing a robust of a solution space.

Over time, these methods have also come to include any procedures that employ strategies for overcoming the trap of the local optimality in the complex solution spaces, especially those procedures that utilize one or more neighbourhood strucutures as a means of defining admissible moves to transition from one solution to another, or to build or destroy solutions in constructive and destructive processes. “

Metaheuristics can be classified into three categories: Local search based, Constructive and Population-based.

2.3.3.1 Local Search based metaheuristics

These type of heuristics are starting from an initial solution and moving to a neighbouring solution while applying minor changes to the solution until the given number of iterations come to an end. Some good known types of Local search are:

 Iterated Local Search

 Tabu Search

 Simulated Annealing

 Guided Local Search

 Variable Neighbourhood Search

(22)

Iterated Local Search (ILS): This metaheuristic extends the local search method to avoid getting stuck in a local optimum, where improving neighbors are not available. ILS modifies the method by repeated calls to the Local Search method. Each time it starts from a new initial solution which usually will end up in a different local optimum.The best of the local optima found is stored and returned when the search is completed.

Tabu Search: Tabu search allows the modifications to the solution which not necessary leads to a better solution. Thus, the method can avoid being stuck in a local optimum, by preventing the search from coming back to previously visited solutions. Tabu search uses memory to keep track of already explored solutions and stores components from the most recent moves in a tabu list to prevent them from being part of a new move within a given time frame. The best solution found overall in the search is stored and returned when the search is usually completed after a given number of iterations.

Simulated Annealing: This metaheuristic is used to solve the type of problems, where finding a good solution in a short time period is important.

Simulated Annealing selects a possible move at random, and uses probability to decide whether to accept a solution or not if the quality is poorer than the previous one. The probability factor decreases during the search, which leads to only good quality solutions will be accepted at the end of the search.

Guided Local Search (GLS): GLS uses penalties to help escape a Local Search method from local optima and progress to find global optima. These penalties are calculated while searching the solution space. The idea is to add penalties to the cost function employed by the Local Search method. A given number of times the repetitions are performed on the Local Search by using local optima and the enlarged cost function that directs the search away from local optima.

Variable Neighborhood Search: VNS is different from other local search based meta-heuristics because it does not explore one single neighborhood, but alters between several different predefined neighborhoods. This means

(23)

that it can escape from a local optimum in one neighborhood by introducing another one.

2.3.3.2 Constructive Meta-heuristics

The complete solution is not considered in this type of metaheuristics. The solution is constructed by addition of one element in each iteration. Unlike the constructive heuristics, global memory is used between several runs of the construction process to store information about the quality of the components. The objective value of a solution is not given until the solution is completed, but then it can be used for guiding the next run of the process. These metaheuristics are constructed in a greedy way, and examples are:

 Greedy Randomized Adaptive Search Procedure(GRASP)

 Ant Colony Optimization

Greedy Randomized Adaptive Search Procedure (GRASP) is based on the repeated sampling of random greedy solutions and improve those solutions by using a local search approach to find local optima. The sampling function builds a Restricted Candidate List (RCL) that controls the selection of the components of a solution. A threshold on the cost of including the component to the candidate solution defines the greediness of the sampling method.

Ant Colony Optimization uses the search history and heuristic information to build the candidate solution and keep the knowledge from solution construction into the history. The solutions are developed separately one at a time by using probability. The selection of component is based on the involvement of component to the overall solution cost and quality of the historic solution from which the component has been included.

2.3.3.3 Population-based Meta-heuristics

These metaheuristics strategy is to look into a group of different solutions.

While, other metaheuristics try to improve individual solutions. The objective here is to find high-quality solutions by interchanging the characteristics between existing solution. The idea is that combining the characteristics of two good solutions could lead to an even better solution. Types of these metaheuristics are:

 Genetic algorithm

(24)

Genetic Algorithm can solve both constrained and unconstrained optimization problems which imitate the way of natural selection. The genetic algorithm randomly selects the component from the population of the solutions and then produce the offspring of the selected components by considering them as parents. As the offsprings are generated over and over, the original population progress towards an optimal solution.

3.0 Problem Description 3.1 Problem Definition

The problem (FSMVRPPD) considered in this thesis includes two major decisions.

First, the construction of a fleet consisting of different types of vehicles, and then routing the heterogeneous fleet of vehicles such that all customer’s demand is fulfilled completely. The storage capacity at customers is not included in the problem. As the fleet includes heterogeneous vehicles, thus each vehicle type has different loading capacity.

Then the question is why a business or company wants networks to design this distribution? The answer is to optimize the transportation costs and to run the business successfully. As the companies have the main goal to achieve the profit from the investments and transportation cost in general accounts for about 1/5^th of the total cost.

Therefore, the objective of FSMVRPPD is to minimize the total cost while fulfilling the customers’ demand. The cost includes the operational cost of using the heterogeneous fleet of vehicles for traveling between the depot and customers in a route, in addition to a fixed cost of acquiring/owning the vehicles in the fleet.

For a general understanding, we can present the objective function as the cost function below:

(25)

The cost function includes the costs of only those vehicles selected for the fleet, in order to serve the customers and the traveling cost for routing the vehicles between the depot and the customers. There will be some decision criteria to find the optimal results about travelling routes and vehicle fleet.

The total cost is calculated by summing up the cost of each route found in the solution.

There are chances that the same type of vehicle can be used on various routes, assuming that the possible number of each vehicle type is unlimited. Therefore, the fixed cost of the selected vehicle type is counted for every route it is assigned to. We can describe the problem by looking at the following rules/constraints:

 There exist a set of heterogeneous vehicle types with different load capacity and fixed cost.

 Only one vehicle can serve a route at a time.

 The fleet can consist of a combination of any number of all vehicle types, and not all vehicle types need to be included in the fleet.

 A customer should be served in only one route.

 All the customers are served from single un-capacitated distribution point/

depot. Each route must start and finish at the depot.

 Customers can have two types of demand; one is delivery, and another is the pickup.

 Some customers can have delivery only and some can have pickup only.

 Both delivery and pickup demand must be fulfilled on a single visit to the respective customer.

 The vehicle capacity cannot be exceeded at any customer in the route.

𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝐹_𝑐 = 𝐹_𝑣 + 𝑇_𝑟

Where, 𝐹_𝑐 – total cost (sum of both cost factors) 𝐹_𝑣 – Fixed dispatch cost of vehicles 𝑇_𝑟 – Travelling cost between all nodes

(26)

3.2 Example

In this section, a small example is presented to make an easier explanation of the FSMVRPPD. In this example, there are five customers with both pickup and delivery demands, two vehicle types with the different capacity fleet and a depot. Figure 3 represent the scenario of the problem. A triangle shape denoted with D accounts for the depot node from where the customers are going to be served. The five rectangles represent the five different customers as c1, c2, c3, c4 and c5. Each customer has a delivery demand denoted as ‘d’ and a pickup demand denoted as ‘p’. The values for each demand are shown near to respective customer.

Figure 3 A VRP problem scenario

Now we create routes to fulfill the customer demands by using the two types of vehicles V1 and V2, with capacities of 35 and 40 respectively. According to the FSMVRPPD explained above, the solution for this example would be as shown in Figure 4.

(27)

Figure 4 Vehicle routing solution to example

The scenario has been solved by using both the vehicles. There are two different routes RED and GREEN, represented by red and green arrows. V1 is assigned to RED and V2 to GREEN. Vehicle V1 serves two customer c2 and c3, while vehicle V2 serves the three remaining customers c1, c4, and c5. On the RED route, the customer has the total delivery demand of 32 units and total pickup demand of 34 units. If vehicle V1 starts from the depot with 32 units, visits c3 where it delivers 15 and picks up 16 units. The load is now 33 units, which still is below the total capacity of 35. Next c2 is visited where 17 units are delivered, and 18 are picked up. The total load is increased to 34 and the vehicle returns to the depot.

On the other hand, vehicle V2 serves the GREEN route. Both delivery and pickup demand is the same i.e. 40 units, so the vehicle is fully loaded when leaving as well as when returning to the depot. We can, however, see that c1 cannot be visited as the first customer on the route since the pickup demand is higher than the delivery demand, which would lead to overload on the vehicle. In this example, c5 is chosen as the first customer on the route, and then the only option to avoid overload is to visit c4 next. Thus, the routes would be:

RED: D c3 c2 D; d=32, p =34; vehicle = V1 (capacity 35)

GREEN: D c5 c4 c1 D; d=40, p=40; vehicle= V2 (capacity 40)

(28)

These routes are a feasible solution to the problem and do not violate any of the constraints of the FSMVRPPD. Still better solutions exist for this instance.

4.0 Mathematical Model for FSMVRPPD

In this section, the mathematical formulation for the FSMVRPPD is presented. This formulation is an extension of the FSMVRP proposed by (Gheysens, Golden, and Assad 1984). Their FSMVRP model has been modified to meet the current problem situation, and the pickup and delivery demand constraints have been formulated and added into the FSMVRP model. In this formulation, each customer is going to be served for both demands (i.e. pickup and delivery) at the same time, or in other words, both pickup and delivery are going to be performed in single visit to the particular customer.

To implement the pickups and deliveries in FSMVRP the following rules have been taken into account:

(i) Feasibility: A solution is feasible if the total quantity assigned to each route does not exceed the capacity of the vehicle which services the route and the vehicle has enough capacity for picking-up the commodities at customers.

(ii) Delivery-feasible: This case means that the total amount of commodities to deliver in a route must not exceed the vehicle’s capacity.

(iii) Pickup- feasible: This rule ensures that the vehicle has enough capacity to pick- up the goods of all the customers of the route.

(iv) Load feasible: The vehicle’s capacity is not violated at any node of the route.

Such a violation can depend on the sequence of the customers even if the route is both Pickup- and Delivery feasible (NEO 2013).

The following are the notations used in the FSMVRPPD formulation:

n – total number of customers

N – set of the nodes, including depot node 0, N= 0,1,….n

(29)

A – set of arcs of traveling possibilities between nodes (i, j), where 𝑖 ≠ 𝑗, ∀ 𝑖 ∈ 𝑁, ∀ 𝑗 ∈ 𝑁 C – set of customers, C=1….n

V – set of vehicle types

𝑄_𝑣 – capacity of a vehicle of type 𝑣, ∀𝑣 ∈ 𝑉 and 𝑄₁ < 𝑄₂ < ….<𝑄_𝑣 𝑓_𝑣 – fixed operation cost of vehicle type 𝑣, ∀𝑣 ∈ 𝑉 and 𝑓₁ < 𝑓₂ < ….<𝑓_𝑣 𝑑_𝑗 – delivery demand of customer 𝑗, ∀ 𝑗 ∈ 𝐶

𝑝_𝑗 – pickup demand of customer 𝑗, ∀ 𝑗 ∈ 𝐶

𝑇_𝑖,𝑗 – cost of traveling from customer 𝑖 to customer 𝑗 , ∀ (𝑖, 𝑗) ∈ 𝐴

𝑌_𝑖,𝑗 - delivery load from customer 𝑖 to customer 𝑗 , ∀ (𝑖, 𝑗) ∈ 𝐴 𝑍_𝑖,𝑗 - pickup load from customer 𝑖 to customer 𝑗 , ∀ (𝑖, 𝑗) ∈ 𝐴

𝑋_{𝑖,𝑗,𝑣} – 1 if vehicle of type 𝑣 travels directly from customer 𝑖 to customer 𝑗, 0 otherwise ∀ (𝑖, 𝑗) ∈ 𝐴 , ∀𝑣 ∈ 𝑉

𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 ∑ ∑ 𝑓_𝑣

𝑗 ∈ 𝑁

𝑋_0,𝑗,𝑣

𝑣 ∈ 𝑉

+ ∑ ∑ 𝑇_𝑖,𝑗

(𝑖,𝑗) ∈ 𝐴

𝑋_{𝑖,𝑗,𝑣}

𝑣 ∈ 𝑉

Subject to

∑ ∑ 𝑋_{𝑖,𝑗,𝑣}

𝑖 ∈ 𝑁 𝑣 ∈ 𝑉

= 1, ∀ 𝑗 ∈ 𝐶

∑ 𝑋_{𝑖,𝑗,𝑣}

𝑖 ∈𝑁

− ∑ 𝑋_{𝑗,𝑖,𝑣}

𝑖 ∈𝑁

= 0, ∀ 𝑗 ∈ 𝐶, 𝑣 ∈ 𝑉

∑ 𝑌_𝑖,𝑗

𝑖 ∈𝑁

− ∑ 𝑌_𝑗,𝑖

𝑖 ∈𝑁

= 𝑑_𝑗, ∀ 𝑗 ∈ 𝐶

∑ 𝑍_𝑗,𝑖

𝑖 ∈𝑁

− ∑ 𝑍_𝑖,𝑗

𝑖 ∈𝑁

= 𝑝_𝑗, ∀ 𝑗 ∈ 𝐶

𝑌_0,𝑗 ≤ ∑ 𝑄_𝑣

𝑣 ∈𝑉

𝑋_0,𝑗,𝑣 , ∀ 𝑗 ∈ 𝐶

𝑍_𝑗,0 ≤ ∑ 𝑄_𝑣

𝑣 ∈𝑉

𝑋_𝑗,0,𝑣 , ∀ 𝑗 ∈ 𝐶

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(30)

𝑌_𝑖,𝑗+ 𝑍_𝑖,𝑗 ≤ ∑ 𝑄_𝑣

𝑣 ∈𝑉

𝑋_{𝑖,𝑗,𝑣} , ∀ (𝑖, 𝑗) ∈ 𝐴

𝑌_𝑖,𝑗 ≤ ∑ 𝑀

𝑣 ∈𝑉

𝑋_{𝑖,𝑗,𝑣} , ∀ (𝑖, 𝑗) ∈ 𝐴

𝑍_𝑖,𝑗 ≤ ∑ 𝑀

𝑣 ∈𝑉

𝑋_{𝑖,𝑗,𝑣} , ∀ (𝑖, 𝑗) ∈ 𝐴

𝑌_𝑖,𝑗 ≥ 0, ∀ (𝑖, 𝑗) ∈ 𝐴 𝑍_𝑖,𝑗 ≥ 0, ∀ (𝑖, 𝑗) ∈ 𝐴

𝑋_{𝑖,𝑗,𝑣} ∈ (0,1), ∀ 𝑣 ∈ 𝑉, (𝑖, 𝑗) ∈ 𝐴

(8)

(9)

(10)

(11) (12) (13)

The objective function (1) outputs the total cost of servicing all the customers to fulfill their demand. The total cost consists of fixed operational cost of vehicles used and the variable cost of the routes used in the solution. Constraint (2) guarantees that every customer is serviced only once, in other words, pickup and delivery operations are performed in the single visit. Constraint (3) states that same type of vehicle that reach a customer must leave the same customer, while constraints (4) and (5) are the flow equations for both delivery and pickup demands of customers, respectively. In constraint (6), it is stated that total delivery load must not exceed the vehicle capacity while leaving the depot. On the other hand, constraint (7) shows that when the vehicle arrives at the depot after serving customers, the pickup load should not violate the vehicle’s capacity. While Constraint (8) ensures that the vehicle capacity must not be violated during the visit to customers on the route. Constraints (9) and (10) represent, respectively, that no delivery and pickup operation will be performed on arc 𝑖 𝑡𝑜 𝑗 if that arc is not served by any of the vehicles. Constraints (11) and (12) state that variables for delivery load and pickup load must be positive number, and in (13), the route decision variable must hold a binary value either 0 or 1.

5.0 Iterated Local Search

In this chapter, we will see the implementation of an Iterated Local Search algorithm on our current problem, and analysis/interpretation of results produced by the algorithm.

(31)

5.1 ILS Algorithm

ILS is a simple metaheuristic approach for solving combinatorial optimization problems. ILS helps a traditional Local Search method to avoid getting stuck in a local optimum by applying some simple modifications to it. The changes to the Local Search method consists in repetitions of it, every time commencing from a new initial point. The starting points are obtained by applying perturbation to the current solution or eventually choosing a random one. Thus, it does not use information obtained from previous Local Search stages but uses memory about previously found local optima to develop better starting points for a Local Search.

5.1.1 General ILS Procedure

This section presents a general procedure for iterated local search as shown in Figure 5:

General Algorithm: Iterated Local Search 1.

2.

3.

4.

5.

6.

7.

Generate: INITIAL_SOLUTION si

s*  LOCAL_SEARCH (si)

- Local solution driven from si

ITERATE until END CONDITION s'  MODIFY (s*)

- Modifies the solution s^* to obtain a random starting point s*' LOCAL_SEARCH (s')

s*  ACCEPTANCE_CRITERION (s*, s*') EXIT

Figure 5 General Procedure for Iterated Local Search

In general, this procedure is implemented as a problem-specific optimization algorithm. By the repetitions of the algorithm, one could obtain significantly good results, but it needs improvements in the search space.

Usually, this algorithm is implemented to optimize cost for combinatorial optimization problems. Suppose, we have a candidate solution s and the set S which contains all possible solutions.

(32)

Let C be a cost function that is to be minimized. The algorithm takes a solution s^’ as input to the local search algorithm, then the local search produces the solution s^*’ with lower or equal cost value than C(s). After each performance of the local search, the resulting solution s^*’ is compared to the previous s^*, and if fulfilling the acceptance criterion (i.e. best so far in the search), it replaces the previous as s^*. (Lourenço, Martin, and Stützle 2010) presented the basin of attraction in Figure 6.

Figure 6 Probability densities of costs

The curve labelled s indicates the left tail of the cost density function for all solutions, while the curve labelled s* indicates the cost density function for the solutions that are local optima (Lourenço, Martin, and Stützle 2010).

In Iterated Local Search the set S* of all solutions s*’ is explained as walking from one s* to a neighbouring one. It is implemented heuristically as below:

- It applies a change or modification to s* (current given) which results as s' - LOCAL_SEARCH operates on s' and produces a solution s*'

- If s*' qualifies the acceptance test, it becomes the next solution to be used as a basis for the search, otherwise s* remains the basis.

This procedure should lead to a large exploration of the solution space if the modifications/perturbations are not too small. In our approach, we are obtaining random solutions by making large modifications to the current solution. On the other hand, smaller modification would often lead the solution back to s* and explore very limited area of the current solution. Diagrammatically the ILS procedure could look as shown in Figure 7.

(33)

Figure 7 ILS procedure

In Figure 7, Starting with a local minimum s*, we apply a perturbation leading to a solution s'. After applying LOCAL_SEARCH, we find a new local minimum s*' that may be better than s* (Lourenço, Martin, and Stützle 2010).

As a summary of this section, we can say that ILS is more efficient when it has biased exploration of the set of local optimal solutions. The exploration effectiveness is directly influenced by the modifications to solutions and acceptance conditions, but the resulting solutions can be better by adjusting the ILS building blocks.

5.2 ILS for FSMVRPPD

This section describes the simple Iterated Local Search (ILS) algorithm implemented for solving the FSMVRPPD. The ILS algorithm follows a very simple technique to iterate over a Local Search method by taking a random starting point every time. The algorithm follows the major steps from Figure 5 where four important procedures have to be defined.

These are: INITIAL_SOLUTION, LOCAL_SEARCH, MODIFY and

ACCEPTANCE_CRITERION.

The initial starting point is generated through the procedure INITIAL_SOLUTION by randomly selecting customers to be served in the routes and assigning vehicle types that meet the demand in each route. Afterwards, there is feasibility check on the generated routes to make sure that the solution is feasible and if so the solution value is calculated. Then the LOCAL_SEARCH is applied on the solution generated by INITIAL_SOLUTION to find

(34)

the local optimum s*. Now, the ILS goes under the iteration phase where MODIFY performs perturbation to the local solution s* from LOCAL_SEARCH and outputs a changed solution s' as a basis for the next LOCAL_SEARCH call. Again, LOCAL_SEARCH is applied to the new solution s' and generates another local optimum s*'. Afterwards, the procedure ACCEPTANCE_CRITERION compares s* and s*' to take a decision on which solution is going to be explored further and which one is going to be discarded. The repetition is bounded by a given number of iterations.

5.2.1 INITIAL_SOLUTION

The ‘init()’ procedure is shown by pseudocode in Figure 8 and starts by initializing the current solution with the total possible number of routes in the given problem. Total maximum routes are calculated by dividing the total delivery demand of all customers by the capacity of the smallest available vehicle, and two extra routes are added to account for differences in delivery and pickup demand. Then the procedure ‘rndSolution()’, described in Figure 9, generates some routes by randomly distributing customers to different vehicle routes until all the customers are assigned to vehicle routes. Afterward, a procedure

‘adjustVehicle()’ in Figure 10 assigns vehicles of the necessary capacities to the routes for meeting the customer’s demands. A solution Si is obtained from the above process and checked for the feasibility on all feasibility constraints. If Si violates one of the feasibility constraints, then the procedure ‘isFeasiblePD()’shown in Figure 11, returns that the solution is infeasible. If solution Si is infeasible, then a large penalty is added to the solution’s objective value to make sure that the solution is not considered as the overall best found during the search. On the contrary, an infeasible solution can still be a good basis for finding good feasible solutions after the Local Search. In Figure 12 the procedure

‘TotalRoutingCost()’ which calculate the total cost of a solution is shown.

Procedure: init () 1.

2.

3.

4.

maxRoutes  (sum of total delivery / smallest vehicle capacity) + 2 SET infeas = TRUE

CALL rndSolution(CurSol_) CALL adjustVehicle(CurSol_)

(35)

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

IF CALL isFeasiblePD(CurSol_) = TRUE THEN - SET infeas = FALSE

CALL totalRoutingcost(CurSol_)

SET CurSolVal_ = total cost of solution ‘CurSol_’

IF CALL isFeasiblePD(CurSol_) = TRUE THEN - PASS feasible_  TRUE

ELSE PASS feasible_  FALSE

Apply infeasible penalty to ‘CurSolVal_’

ADD big amount to cost of solution EXIT.

Figure 8 Initialization procedure

Procedure: rndSolution(Solution &SOL) 1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

Set vIter

Set noVehicle  number of routes from SOL -1 Repeat FOR matrix size ‘n()’

- temp  dimension value of matrix END of FOR loop 3.

DO WHLE ‘count’ > 1

- count  size of matrix

- randNo  random number in range of ‘count’ +1 - vIter  point to ‘randNo’

IF randNo does not point to depot node - vTyp  random vehicle type +1

- RouteNo  random number in range of ‘noVehicle’ +1 - CALL setVehtypRoute (RouteNo, vTyp)

- CALL addCusRoute (RouteNo, temp[randNo]) END of IF

Delete element pointed by ‘vIter’

END of DO-WHILE loop 6.

Figure 9 Procedure for creating a random solution

(36)

Procedure: adjustVehicle(Solution &SOL) 1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

vsize  Get number of routes in SOL Repeat FOR vsize

- cRoute  Get number of customers in current route ‘vsize’

Repeat FOR cRoute

- t_demand  calculate total delivery - t_pickup  calculate total pickup END of FOR loop 3.

Get total vehicle type ‘noVtypes()’

Repeat FOR noVtypes

- IF t_demand & t_pickup <= capacity of current vehicle ‘k’

- Change vehicle type to ‘k’ in route ‘vsize’

- BREAK - END of IF END of FOR loop 6.

END of FOR loop 2.

Figure 10 procedure for adjusting the vehicle to the best fitted for meeting the customer demand on the route

Procedure: isFeasiblePD (Solution &SOL) 1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

vsize  get number of routes in SOL

IF vsize == 0 THEN return FALSE and exit.

Repeat FOR each route ‘vsize’

- vType  number of vehicle type

- capacity  capacity of vehicle type ‘vType’

- cRoute  number of customers in route ‘vsize’

Repeat FOR each customer ‘cRoute’

- sumDemand  calculate total delivery demand in route ‘vsize’

- sumPickup  calculate total pickup in route ‘vsize’

- IF sumDemand OR sumPickup > capacity THEN return FALSE and exit.

END of FOR loop 7.

INITIALIZE currLoad  sumDemand Repeat FOR each customer ‘cRoute’

- Subtract delivery ‘d_’ for each customer from ‘currLoad’

(37)

15.

16.

17.

18.

19.

- Add pickup ‘p_’ for each customer into ‘currLoad’

- IF currLoad > capacity THEN return FALSE and exit.

END of FOR loop 13.

END of FOR loop 3.

Return TRUE.

Figure 11 Procedure for checking whether a solution is feasible or not

Procedure: totalRoutingcost (Solution &SOL) 1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

INITIALIZE sum =0

Repeat FOR each route ‘vsize’

- cRoute  number of customers in route ‘vsize’

Repeat FOR each customer in ‘vsize’

- sum  calculate edge cost END of FOR loop 4.

typ  vehicle type in route ‘vsize’

cost  fixed cost of vehicle type ‘typ’

sum  sum + cost END of FOR loop 2.

RETURN sum.

Figure 12 Procedure for calculating the total cost of a solution

5.2.2 LOCAL SEARCH

The pseudo code for the Local Search is shown in the procedure ‘runSolver ()’ in Error! Reference source not found.. The local search procedure ‘runSolver()’ in explores the neighbourhoods until an un-improved solution is found. In the very beginning of

‘runSolver’ procedure, the random initial solution Si set to be the current best solution s*.

Then, the repetition starts to perform the local search while the solutions are getting improved. Next step is to collect information from the current solution s* and pass that information to the appropriate variables used in the local search procedure ‘runSolver’. A very large value (i.e. DBL_MAX) is initialized as the best neighbourhood value BN, so that the solutions with large values could be explored. Next, the repetition on the total number of routes in the current solution s* begins to explore the neighbourhoods inside the current

(38)

solution space. Inside the loop over the routes, an another loop is used to get the customers from the current route. Further inside the loop over number of customers, the number of total routes are repeated to get two different neighbourhoods for exploration. The information on the vehicle’s capacity for the current route is collected. Then, a conditional statement validates the vehicle capacity constraint. The vehicle capacity constraint should not be violated. If the conditional statement mentioned in later sentence outputs a Boolean TRUE value, then a neighbourhood N1 by adding the current customer to the current route will be used. Otherwise, a neighbourhood N2 by swapping the customers between two different routes will be used. The optimization procedures from Error! Reference source not found.

are applied to the neighbour N1 or N2 to obtain the optimality. Afterwards, the feasibility procedure in Error! Reference source not found. checks whether the new solution s*' is acceptable or not. If the solution s*' found from the neighbourhood N1 or N2 is feasible and better than the best neighbourhood value BN, then the best neighbourhood value BN will be initialized with the current found solution s*'. Otherwise, the infeasible solution s*' would lead to add penalty to objective value to escape from the infeasible solution space. After the completion of the repetitions on all of the routes in the solution s*, the best neighbourhood value BN is compared with value of the current solution s*'. If the best neighbourhood value BN is better than the value of the solution s*' and if the solution s*' from the neighbourhood is feasible, then the best neighbourhood value BN will be set as the new current best solution s* value and search will continue to improve the solution further. Otherwise, if no improvement is found from the neighbourhood N1 or N2, the local search will be stopped and output the current best value as the solution to the current search.

Procedure: runSolver() 1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

START clock

noRoutes  number of routes in ‘CurSol_’

SET BestSol_ = CurSol_

SET BestSolVal_ = CurSolVal

SET BestNeighborVal_ = very large value WHILE improving = TRUE

SET improving = FALSE

- Previous solution  Current solution - Get maximum value for neighbour Repeat FOR each route I in ‘noRoutes’

The fleet size and mix vehicle routing problem with pickups and deliveries

Master’s degree thesis

LOG950 Logistics