Variable Neighborhood Search Algorithm for the Variable Cost and Size Bin Packing Problem

Variable Neighborhood Search Algorithm for the Variable Cost and Size Bin Packing Problem

Héctor J. Fraire-Huacuja (National Institute of Technology of Mexico, Mexico & Technological Institute of Ciudad Madero, Mexico), Alejandro Estrada Padilla (National Institute of Technology of Mexico, Mexico & Technological Institute of Ciudad Madero, Mexico), Laura Cruz-Reyes (National Institute of Technology of Mexico, Mexico & Technological Institute of Ciudad Madero, Mexico), Claudia Gómez-Santillán (National Institute of Technology of Mexico, Mexico & Technological Institute of Ciudad Madero, Mexico), Nelson Rangel-Valdez (National Institute of Technology of Mexico, Mexico & Technological Institute of Ciudad Madero, Mexico), María Lucila Morales-Rodríguez (National Institute of Technology of Mexico, Mexico & Technological Institute of Ciudad Madero, Mexico) and Juan Frausto (National Institute of Technology of Mexico, Mexico & Technological Institute of Ciudad Madero, Mexico)
DOI: 10.4018/978-1-5225-8131-4.ch001

Abstract

A company that transports goods to supply customers usually needs to plan the routes that the fleet must follow, since transportation means a high percentage of the value added to goods. The vehicles must be loaded with the products located in the warehouse to fulfill the orders requested by customers. Many enterprises use order batching and picking systems to improve the warehouse management. This chapter describes a novel algorithm based on the methodology of variable neighborhood search for the variable cost and size bin packing problem. This problem considers that the sizes and costs of the bins can be different and there is no correlation between them, which is a sensible assumption for the order batching process in many applications. A series of computational experiments were conducted with a set of hard instances to validate this approach. The results show that the proposed algorithm outperforms the state-of-the-art algorithm, and a statistical hypothesis test is used to support the obtained conclusions.
Chapter Preview
Top

Introduction

Logistics systems applied to transport procedures are a current problem in the productive and service sectors. Distributors should stock customers effectively and efficiently with products, which constitutes a major challenge for a logistics system since resources are limited, and transportation costs constitute a high percentage of the value added to goods.

According to Lambert, Stock & Ellram (1998), every logistics system has warehousing as an integral part for the proper development of its related activities. The warehousing represents a link between producers and customers that is formed by a constant delivery of products that must be ensured within an adequate consumption of resources (e.g., time, space, money, etc.). The goal of warehousing is to serve as final or intermediate storage of products (which could be raw materials or finished goods, among others).

Based on Lambert et al. (1998) and de Koster, Le-Duc & Roodbergen (2007), the operations that should be made in a warehouse can be divided into four main functions, which are: 1) Receiving, which is related to the unloading of products from transportation vehicles to receiving docks; 2) Transferring, which involves the movement of the products from receiving docks to assigned storage locations; 3) Order picking, which consists of collecting the required product quantities from storage to satisfy customer orders; and, 4) Shipping, which involves loading products into transportations that are ready to deliver the products. In general, solving these real-life world transportation problems is a complex task because it requires solving different NP-hard problems such as loading, routing and scheduling the fleet vehicles to satisfy the customers demand of products located in the warehouse system of the company.

Particularly, the Order Picking Operation (OPO) accounts for up to 50% of the total warehouse operating costs (Frazelle, 2001; Bódis, Botzheim & Földesi, 2017), and because of this, it has recently turned into an area of interest in the scientific community for improving productivity in warehouses (de Koster et al., 2007). Inside the OPO confluent three decision areas, storage policy, order consolidation policy, and routing policy, and according to Wäscher (2004), the consideration of all of them into one single optimization problem could lead to globally optimal solutions. However, the development of strategies that deal with such a problem is rarely done in practice because it is computationally intractable, and instead, researchers focus on one or two of these decision areas simultaneously, while in practice decisions are made sequentially (de Koster et al., 2007).

Based on the classification proposed by Dallari, Marchet & Melacini (2009), the OPO can be done through different approaches called Order Picking Systems (OPS). Of interest in the present research is the picker-to-parts system which involves the selection of products by humans or vehicles to optimize a batch of orders that could result in significant savings in labor costs (Horvat, 2012). Mainly, the optimization in such OPS focuses on reducing the total order picking time (Wäscher, 2004), a time that for a single tour depends on the travel, search, picking and set-up times (de Koster, Roodbergen & van Voorden, 1999; Henn, Koch & Wäscher, 2012).

The organization of the customer’s orders affects all the previously mentioned times. First, determining which orders must transport a vehicle during each trip impacts in the search and set-up times because it can reduce the number of trips required (or even the number of vehicles that can be used simultaneously); this activity associated with the Order Batching Problem, or OBP (cf. Won & Olafsson, 2005). After that, once that the particular order configuration has been identified, the route followed by the vehicle through the products’ isles of the storage to pick the indicated orders impact in the travel and picking times because the longer the route the longer the spent time; this activity is related to the Order Picking Problem (OPP) (cf. Won & Olafsson, 2005). Note that both problems, OBP and OPP, are associated with the Order Picking Optimization in warehouses.

Complete Chapter List

Search this Book:
Reset