Order picking: modelos e algoritmos de roteamento

Abstract

This paper examines the vehicle routing problem for order picking within warehouses. The objective is to minimize the number of vehicles needed to pick all of the demand and return to the depot within a given amount of time, which represents the warehouses service level. Each vehicle can pick all of the demand in a given location or a fraction of the total demand, leaving part of the demand to be picked by another vehicle. The problem can be classified as the vehicle routing problem with split pick-ups and service level constraints considered as a form of time windows (VRPTWSP). Two new optimization models are presented for this problem: a static model and an on-line model. The static model considers the case in which all of the vehicles are at the depot. The on-line model considers the case in which the vehicles have already left the depot and can alter their original routes to pick newly received items on the same route. Computational results for the two models are given.In addition to these two new formulations, a heuristic for generating upper bounds and a new class of valid inequalities which tightens the lower bounds are presented.