Solving the multi-depot vehicle routing problem with a time window using an efficient meta-engineering algorithm

Dissertation for obtaining a master's degree in industrial engineering

Fall 1392

Abstract

During the past years, many efforts were made to reduce the cost of transportation by using different models of the vehicle routing problem. In fact, the increase in transportation costs has encouraged many to reduce the cost of transportation related to their profession by using a vehicle routing system. In this research, we examine the multi-warehouse vehicle routing problem with a time window. The multi-warehouse vehicle routing problem with a time window includes a fleet of vehicles that depart from the warehouses, meet a group of customers, and return to the warehouse. In this research, we have considered a situation where it is no longer necessary for each vehicle to return to the starting warehouse after meeting customers, but the warehouse at the beginning of the route may be different from the warehouse at the end of the route. Each vehicle has a fixed capacity, and each customer has a specific demand that must be fully satisfied. The problem consists of combining meeting selection for each customer and determining vehicle routes based on the rules of the vehicle routing problem; So that the total distance traveled by each vehicle and the total times of early and late arrivals and the total total cost are minimized. Since the vehicle routing problem is a problem belonging to the NP-Hard class, the multi-warehouse vehicle routing problem with a time window is also a generalization of VRP, which is part of complex problems belonging to the NP-Hard class, and meta-heuristic approaches are used to solve it. In this thesis, a genetic algorithm is proposed to solve the problem of multi-warehouse vehicle routing with a time window. An attempt has been made to categorize customers by using the genetic clustering method to reduce the search space of the problem, and then by using the genetic algorithm, we obtain the answer set and the objective function of the problem. Keywords: vehicle routing, multi-warehouse, time window, clustering, genetic algorithm. Chapter 1. General research.

-1- Introduction

The increasing development of urbanization, industries, especially support industries, has turned the movement of people and goods into a problem whose complexity is constantly increasing. Urban growth has caused an increase in the demand in the transportation industry, which has caused large cities and industries to face many problems in the fields of traffic congestion, air pollution, long time wasted on people's daily trips, increased fuel consumption and depreciation of vehicles, etc.

To solve traffic problems and the resulting economic, social and environmental issues in large cities, manufacturing industries and the service sector, a well-equipped and efficient transportation system is needed. May be As a result, there is a growing demand for solutions that are effective and can achieve all the expected benefits, including cost savings, taking into account maximum service and optimal use of capital and equipment. Intra-organizational transportation, bus routes, school services, distribution and maintenance systems, money distribution and banking services, and industrial waste collection, etc. are among the issues that can be mentioned.

Transportation planning is one of the basic and important fields nowadays in various branches of science such as operations research, industrial engineering, and civil engineering. May be The main goal of this field is to minimize the cost of transporting goods and materials between the two levels of producers and consumers, so that the demand of each consumer must be satisfied by producers. In this case, according to the type of problem, factors such as the length of the road, quality of the road in terms of structure and environment, road traffic, capacity of vehicles, etc. are taken into consideration. If there are intermediate levels in addition to the producer and consumer levels, it is called a transportation network. As an example, the routing of intra-city buses is a special mode of the transportation network. 1-2- Necessity and importance of transportation planning Transportation is one of the major and important sectors of the economy of any country.

1-2- Necessity and importance of transportation planning

Transportation is one of the major and important sectors of the economy of any country, and it is also one of the most important sectors that make up the cost of final products. The increasing development of urbanization, industries, and especially support industries, has made the movement of people and goods a problem whose complexity is constantly increasing. Urban growth has caused an increasing increase in demand in the transportation industry, which, as a result, has caused large cities and industries to face many problems in the fields of traffic congestion, air pollution, long time wasted on people's daily journeys, increased fuel consumption and depreciation of vehicles, etc. To solve traffic problems and economic, social and environmental issues arising from them in big cities, manufacturing industries and service sectors need a well-equipped and efficient transportation system. As a result, there is an increasing demand for solutions that are effective and can achieve all the expected benefits, including cost savings, taking into account maximum service and optimal use of capital and equipment. Street cleaning, intra-organizational transportation, bus routes, school services, money distribution and maintenance systems, banking services, and industrial waste collection, etc. are among the issues that can be mentioned. It has been seen in the effective management of goods procurement and distribution system services. A large number of real-world applications, both in North America and Europe, have amply demonstrated that the use of computerized routines for planning the distribution process results in significant savings (typically between 5% and 25%) in general transportation costs. In fact, the transportation process includes all stages of production and distribution systems. The success of using research techniques in operations owes to the development of computer systems both in terms of hardware and software and the increase in the integration of information systems of production and business processes. Another success factor that is extremely important is the development of modeling tools in recent years. In fact, the proposed models account for all the characteristics of distribution problems in real applications, and the corresponding algorithms and computer implementations, and provide good solutions for real examples. Global finds in a reasonable amount of time. (Tath and Associates, 2002).

(Tables and pictures can be seen in the main file)

1-3- Transportation in Iran

The transportation sector as one of the important economic sub-sectors of the country whose production at fixed prices has a higher growth rate than the growth rate of the national economy needs more attention in the country's management system. Examining the statistical data of national accounts in the period between 1370 and 1386 shows that the share of transportation activities in the gross national product has increased during this time period. The increase in the relative share of transportation, warehousing and communication sector from this performance at the national level was 2.8 percent. Table (1-1) shows the comparison of the value of transportation in the gross national product in the country in the years 1370 to 1386. (Shariat, 2004).

 Thus, in the process of economic developments, the transportation sector in the years after the revolution, especially land transportation, has gained more prominence and has been the main support for the movement of cargo and passengers, therefore, considering the high volume of added value of this sector, the importance of investigating and planning transportation in Iran in order to reduce A part of the relevant costs has been felt and a scientific and logical approach to this important issue is necessary.

1-4- The purpose of the study

Transportation planning, nowadays one of the basic and prominent fields in various branches of science, such as transportation, has an important place in economic, production and service systems and is a significant part of the gross national product of any country. owns The problem of vehicle routing is one of the most important problems of transportation planning, which has received a lot of attention from researchers and scientists today. The goal in this matter is to satisfy all demands with minimum cost.