A hybrid local search for the trailers waiting time minimization in warehouse logistic
Alexey Ratushny, Yury Kochetov, Polina Kononova
We study the following scheduling problem for warehouse management. The warehouse consists of some buildings. Each building has given locations (rooms) with known capacity. Each room has only one type of product. Each building has two gates. One gate is for the loading/unloading trailers, another one is for two forklifts from the central zone. The central zone is a production line. It produces some products which must be placed in the warehouse. We know how the central zone is working during each day, i.e. when each pallet (unit) becomes available for putting away. Outbound trailers come to pick some units of a product from the warehouse. Inbound trailers come to put away some units of a product into the warehouse. We know the arriving time for each inbound/outbound trailer and its unloading/loading time. At most one forklift can work in each building at a time. Exactly one forklift can service an inbound/outbound trailer. Our goal is to assign all trailers to buildings and find scheduling for service all the inbound/outbound trailers with the minimal total waiting time. To solve small instances of the problem, we design a mixed-integer linear program for the case all trailers are serviced by the rule First In, First Out for each building. For real-world instances, we design a hybrid local search algorithm based on a multi-agent system, a randomized heuristic with three types of agents: I, G, and M. The I-agents are free trailers that need to be scheduled, whereas the G-agents are groups of trailers already assigned to buildings. The I- and G-agents are driven by their goals (own waiting time). The M-agent acts as the system's manager of the independent intelligent agents and uses a local search to improve the current solution. Computational results for 6 buildings, 50 products, and 90 trailers are discussed.
A Variable Neighborhood Search Based Matheuristic for the Drilling Rig Routing Problem
Igor Kulachenko, Polina Kononova
In this research, we discuss the real-world Split Delivery Vehicle Routing Problem with Time Windows (SDVRPTW) for drilling rig routing in Siberia and the Russian Far East. There is a set of objects (exploration sites) requiring well-drilling work. Each object includes a known number of wells that need to be drilled within a given time interval. Several drilling rigs can operate at the same object simultaneously, but a rig that has started the work on a well completes it to the end. The objective is to determine a set of routes (including the number of wells to drill) for a fleet of drilling rigs to traverse in order to perform all well-drilling requests in time with minimal traveling costs. The main difference with traditional SDVRP is that it is the service time that is split, not the demand, and there is only a limited number of studies concerning such problems. To find high-quality solutions, we design the Variable Neighborhood Search (VNS) based matheuristic. Exact methods aimed at improving the distribution of the well-drilling work are integrated within a VNS algorithm solving the routing part of the problem. Time-window constraints are relaxed, allowing infeasible solutions during the search, and effective evaluation techniques are applied to treat them. We present results of computational experiments for instances with up to 300 objects, 50 rigs, and 365 days in the planning horizon.
Simplicial vertex heuristic in solving the Railway arrival and departure paths assignment problem
Damir Gainanov, Nenad Mladenovic, Varvara Rasskazova
This paper considers a fast solving the practical problem in railway planning and scheduling. i.e., the problem of assigning given arrival and departure railway paths to routs. This problem is to execute as fully as possible the train traffic across the railway station, using a fixed amount of the resources. It appears that the problem may be solved by using any efficient maximum Independent set algorithm, which is known to be NP-hard. On the other hand, Simplicial vertex test is known heuristic that gives good quality solutions on sparse graphs. So, for solving the maximum independent set on sparse graphs, we propose an efficient heuristic based on the extended simplicial vertex test.