The article presents a method for finding the best solutions to the vehicle routing problem with time windows. The proposed algorithm is an implementation of sequential simulated annealing. A new form of the transition function was used, which allows for obtaining near-optimal solutions very quickly.1. INTRODUCTION
The transport of material goods is a very important element of human activity.
Proper management of the distribution network and vehicle fleet allows for a significant reduction in delivery costs.
Currently, in the ERP systems market, an increased demand for applications supporting route planning can be observed [6]. This is related to the fact that even small savings on individual shipments allow for significant cost reductions in the long term. Proper shipment management allows for better fulfillment of customer needs, which helps improve the company’s image.
2. VEHICLE ROUTING PROBLEM WITH TIME WINDOWS
The Vehicle Routing Problem (VRP) is an extension of the traveling salesman problem. In the delivery problem, vehicles with a specified load capacity move between a set of customers. Each customer has a specific demand for goods, and the order of visiting them does not matter. Each route starts and ends at the same place, at the central warehouse. Solving the delivery problem means finding the shortest total length of all vehicle routes, while the load capacity of each of them cannot be exceeded.
In the Vehicle Routing Problem with Time Windows (VRPTW), in addition to the assumptions adopted in the classic VRP, each customer has a defined earliest possible delivery start time ei and the latest possible start time fi. These values define the so-called customer time window. Each customer has a specified service duration si, which is the period during which the vehicle stays at the customer’s location.
The delivery problem was formally described by Solomon [8, 9] in 1987. He prepared a set of problems that are used to test algorithms and to compare research results with currently existing best solutions. In this article (…)
The article contains 19335 characters.
Source: Logistyka Magazine