A Heuristic Algorithm for the Inner-City Multi-Drop: Container Loading Problem

A Heuristic Algorithm for the Inner-City Multi-Drop: Container Loading Problem

Li Pan, Sydney C. K. Chu, Guangyue Han, Joshua Zhexue Huang
Copyright: © 2013 |Pages: 20
DOI: 10.4018/978-1-4666-2925-7.ch014
OnDemand:
(Individual Chapters)
Available
$33.75
List Price: $37.50
Current Special Offers
10% Discount:-$3.75
TOTAL SAVINGS: $3.75

Abstract

Economic globalization, increasing fuel cost, and environmental problems provide a strong stimulation for inner-city container carriers to utilize container space more efficiently in transporting goods for multiple clients during a single round trip. A wall-building heuristic algorithm based on the binary tree data structure is proposed to solve the container loading problem with multi-drop constraints. A dynamic space decomposition approach, together with a repacking and space amalgamation strategy, permits an efficient and effective loading plan to pack containers, illustrated by numerical experiments.
Chapter Preview
Top

Introduction

As the speed of urbanization in the world increases and the values of urban land rise quickly, city logistics activities are becoming a vital factor in sustainable development of cities. Taniguchi et al. (2001) defined city logistics as “the process of totally optimizing urban logistics activities by considering the social, environmental, economic, financial, and energy impacts of urban freight movement.” The most frequent logistics activities are transportation of goods from distribution centers (DCs) to retail shops and supermarkets to ensure urban citizens’ daily consumptions. In modern cities, the distribution centers are often located in the outskirts of cities, supermarkets are built in a few downtown commercial districts, and retail outlets are scattered all over the place in cities. To many cities, it is a huge challenge to facilitate city logistics activities with limited road network capacity to satisfy population needs. Information technology is an important means to improve efficiency of city logistics activities.

In this paper, we study the activities of truck loading/unloading in city logistics to improve utilization of truck volume and efficiency of truck loading/unloading operations. We particularly consider the problem of multiple unloading sites in a single trip. Improvement of such activities can reduce transportation costs, as achieved by vehicle routing (Murakami & Morita, 2010), and also help reduce inventory costs of retail outlets and supermarkets which are concerned in supply chain management (Mahamani et al., 2008; Mohebbi, 2010).

Truck loading problem can be seen as a particular case of container loading problem. The general container loading problem is to orthogonally pack a subset of some three-dimensional rectangular boxes into a rectangular container of fixed dimensions. Each box must be completely contained in the container and cannot overlap with other boxes. Generally, 3D container loading problems fall into the following classifications, depending on the objective function and constraints on the packed items.

Knapsack Loading Problem

For knapsack loading, each item has an associated profit and the problem is to choose a subset of items that can be packed into a container with fixed dimensions and maximize the total profit of all packed items. When the profit of items is set to be their volume, it is equivalent to maximize the volume utilization. This problem has been considered by Gehring et al. (1990) and Pisinger (1997).

Strip Packing Problem

In this problem, the container has fixed length and width, but infinite height. The objective is to pack all items into this container such that the height of container is minimized. Several algorithms for solving this problem are discussed and compared in Bischoff and Marriott (1990).

Complete Chapter List

Search this Book:
Reset