Πλοήγηση ανά Επιβλέπων "Tarantilis, Christos"

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω

Τώρα δείχνει 1 - 1 από 1

Local search algorithms for the pickup and delivery problem with cross-docking
Fidanis, Ioannis; Athens University of Economics and Business, Department of Business Administration; Athens University of Economics and Business, Department of Marketing and Communication; Tarantilis, Christos
The efficient management of a distribution network is crucial for logistic companies and transportation service providers. Transportation costs represent a large percentage of the logistics costs. The costs associated with transport, have a direct impact on the final value consumers must pay. Therefore, the academic community and practitioners have put substantial effort in conducting research for finding optimal ways to decrease transportation costs and increase customer service.The Vehicle Routing Problem (VRP) represents a class of problems that are commonly encountered by transportation companies. In its general form, the objective of the VRP is to design a set of minimum cost routes in order to serve a set of customers under several constraints. Large scale VRPs are very difficult to be solved optimally by an exact algorithm and thus, approximate methods have been developed in order to address these problems and produce solutions of high quality.In practical applications, the distribution of products from a set of suppliers to a set of customers can be performed through two different distribution strategies: i) direct-shipping, and ii) cross-docking. A Cross-dock (CD) can be considered as an intermediate station for consolidating shipments from various suppliers, before delivering them to their final destinations.This work studies a distribution network where both of the aforementioned strategies may appear and it is referred in the literature as the Pickup and Delivery problem with Cross-Docking (PDPCD). The objective of this problem is to find the least cost set of vehicle routes for distributing products from a set of suppliers to a set of customers. The cost representation may vary through various implementations. In this work, the total transportation cost is considered to be the total routing cost (or total distance travelled).Three different algorithms are introduced in order to solve the PDPCD problem. The first algorithm is a Greedy Algorithm which is based on the best decision that can be made at each step of the execution. A vehicle starts from the origin point (depot or CD) and visits the closest node to its current position. It continues visiting nodes till any of the predefined problem’s constraint is met (capacity and time constraints). At this point, a decision is made whether the vehicle will return to the origin point or it will start delivering the loaded goods. This procedure is being repeated for all the vehicles and until all the nodes are served. At the end of this algorithm, a total transportation cost is calculated.Next, we present two tabu search algorithms in an effort to improve the initial solution. For this purpose, two different move types are applied: a relocation move type and an exchange move type. The relocation move aims to reduce the total cost by relocating a node from a vehicle to another vehicle. The exchange move aims to reduce the total cost by exchanging two nodes with each other belonging to different vehicles. The tabu search algorithm introduces a tabu list to forbid certain moves from being applied to the current solution. Moves are considered feasible if they do not violate any of the problem constraints. In addition, an enhanced tabu search algorithm is developed which is able to simultaneously consider both move types at each execution step. The algorithm selects the best solution out of them as the candidate one at each step. We examine the impact on the total routing costs compared to the simple tabu search algorithm.Various computational experiments are conducted in order to examine the performance of the two developed algorithms on benchmark problem instances of the literature. For this purpose, we investigate the impact on total routing costs by using the simple tabu search algorithm considering only a move type each time, as well as the enhanced tabu search algorithm which considers both move types simultaneously.