An Integrated Heuristic Approach for the Period Ve

for the Period Vehicle Routing Problem

with Simultaneous Delivery and Pickup

Ahmad Rusdiansyah

Ahmad Rusdiansyah

Tsao Lab., Department of Industrial Engineering and Management, Tokyo Institute of Technology, Address : O-okayama 2-12-1, Meguro-ku, Tokyo 152-8552 Japan.

Fax +81-30-5734-2947. E-mail Address: arusdian@ie.me.titech.ac.jp

De-bi Tsao

Department of Industrial Engineering and Management,

Tokyo Institute of Technology, Tokyo, Japan

Abstract

This paper introduces an integrated approach for solving the Period Vehicle Routing Problem with Simultaneous Delivery and Pickup (PVRPSDP). The problem considers a dis tribution system consisting of a warehouse and many dispersed location retailers, where each of which having two type of demands to be delivered and collected, respectively. A fleet of capacitated vehicle is employed for delivering products from the warehouse to the retailers, and collecting the reusable empty-containers in the reverse direction for all day during a given T-day period. Precisely, at each retailer’s location, a pickup operation must be established immediately after a delivery operation. The retailers are typically required to be visited once or several t imes over the period, and once a day at the most. The days of visits must follow one of the allowable visit-day patterns that were built based on stationary-interval inventory property. The objective of the problem is to minimize the inventory and traveling system-wide costs subject to the vehicle capacity constraint. We highlight the influent role of the visit frequency. Instead of a given parameter, t he visit frequency for each retailer is treated as a decision variable, and dynamically determined. The novelty of our integrated approach is comprised in maintaining the appropriate balance between the inventory costs and the traveling costs to seek the best visit frequency for each retailer while constructing the tours. We develop heuristic algorithms for the PVRPSPD and establish some experiments to show the performance and the behaviour of our approach.

Keywords: PVRPSDP, delivery and pickup, system-wide costs, visit frequency, heuristics.

Text

The Period Vehicle Routing Problem (PVRP) has received considerable attention over the last two decades. The PVRP is generally viewed as a period version of the well-known Vehicle Routing Problem (VRP) working with a given planning horizon of T-day period. Many efforts in the literature have been established to extend the basic PVRP model to incorporate additional constraints or different objective functions. One of the extensions of the PVRP considered in this paper is that accomodates such business environments where the company - generally driven by environmental or economical motivation - is not only responsible for the distribution of products from a warehouse to the retailers but also the transportation of the reusable empty-containers of the products in reverse direction. For example, in the soft drink industries, the company deals with the distribution of the full-bottles as well as the redistribution of the empty-bottles [1]. The extension problem is named Period Vehicle Routing Problem with Simultaneous Delivery and Pickup (PVRPSDP). This paper introduces an integrated heuristicapproach for solving the PVRPSDP by integrating inventory and vehicle routing decisions. The PVRPSDP here is more viewed as such a tactical-level decision topic of the Inventory Routing Problem s (IRP) rather than such a periodic routing problem. The basic principle at issue in this approach is that the solution must be based on the minimization of system-wide cost consisting of inventory and traveling costs, instead of only traveling cost as do most of PVRP literature.

Consider a distribution system consisting of a warehouse acts a transshipment node and many dispersed location retailers, each retailer is correlated with two quantities representing the demands to be delivered and picked up, named delivery demands and pickup demands respectively, while the warehouse is the origin and the destination of each demand respectively.

The warehouse is assumed to have the autonomy of maintaining inventory levels of products at the retailers. The warehouse has the capability to make decisions regarding size of delivery demands, visit frequency and timing of replenishments for each retailer. By having such authorithies, the warehouse deals with minimizing simultaneously the inventory costs at the retailers and the traveling costs occurred. Note that the size of pickup demands follows a given proportional ratio the the size of delivery demands.

The retailers are typically required to be visited once or several times during the given period, and once a day at the most, where the number of visits is called visit frequency. Based on the stationary interval property of inventory [2],[3], the visits to the retailers have to follow a constraint, named visit-day pattern constraint, which regulates the intervals between two consecutive visits of such a visit-day pattern must be equal. For example, if a retailer requires to be visited 2 times during a 6-day period which is particularly concerned in this research, the retailer will be visited on the days of one of the allowable visit-day patterns; Monday-Thursday, Tuesday-Friday, or Wednesday-Saturday. No other patterns would be acceptable.

Each day during the T-day period, m vehicles with given capacity starting from the warehouse, visits a subset of retailers, and finally returns to the depot. The vehicle transports delivery demands originating in the warehouse to the retailers, and, if necessary, collect their pickup demands to be brought about to the warehouse. To avoid redundant handling activities, at each retailer location, the delivery operation and the pickup operation are assumed to be simultaneously performed by the same tour. Precisely, each pickup operation must be established immediately after the delivery operation. Along each tour, the total load of a vehicle must not exceed the vehicle capacity.

Formally, the objective of the PVRPSDP is to simultaneousl y seek the best visit frequency and the best visit-day pattern for each retailer, and constructing the best vehicle routes for each day of the T-day period, such that all delivery and pickup requirements are fulfilled and the system-wide costs occurred are minimized subject to the vehicle capacity constraint.

We highlight the influent role of the visit frequency, since it is not only a requirement for establishing vehicle routes but also a key factor for minimizing inventory costs. Instead of a given parameter, the visit frequency is treated as a decision variable, and dynamically determined during the construction of the vehicle tours. To search for the best visit frequency for each retailer, we gradually increase the visit frequency, starting from the smallest allowable value to the largest one as developed in [4]. The increase of visit frequency will reduce the inventory cost and increase the traveling cost. The visit frequency will be increased only if the reduction of the inventory cost is greater than the increase ofthe traveling cost while the visit-day pattern and vehicle capacity constraints are satisfied. We also introduce two parameters which represents the weight factors of inventory cost and traveling cost respectively. The weight factors are applied to facilitate decision makers in measuring the degree of importance of each cost from his prespective.

To our knowledge there is no paper dedicated to the PVRPSDP. However, some substansial PVRP literature such as [5],[6],[7],[8],[9] and the papers related to the routing problems with simultaneous delivery and pickup such as [1 ],[10],[11] are briefly reviewed in this paper.

Since the PVRP is known as an NP-hard problem, accordingly, the problem is at least as difficult as the PVRP, so the development of a heuristic method is preferred We develop 2 types of heuristic algorithms that can solve both single vehicle and multi-vehicle problems. T he solution algorithms are divided into two main phases: initialization phase and improvement phase. The initialization phase is to establish i nitial vehicle routes with t he best visit frequency for each retailer. This phase attempts to seek the best visit frequency by evaluating the saving of system-wide costs while constructing initial vehicle routes. The improvement phase employing an efficient tabu search method and 2 opt method, is to improve the current solution by concurrently s eeking the best visit-day pattern for each retailer and the best sequences for all tours. In this phase two types of moves, re-insertion and exchange moves are applied here to interchange the visit-day patterns and the sequences. We perform some experiments to show the performance and the behaviour of the approach using some generated numerical examples.

References

[1] Dethloff J., “Vehicle Routing and Reverse Logistics: The Vehicle Routing Problem with

Simultaneous Delivery and Pickup”. OR Spektrum 23:29-96 (2001)

[2] Bramel, J, and D. Simchi-levi, “The Logic of Logistics, Theory, Algorithms and Applications

for Logistics Management”, New York: Springer. (1997)

[3] Rusdiansyah, A. and Tsao, De-bi, “The Integrated Inventory and Period Vehicle Routing

Problem: A Heuristic Approach”, a paper presented in INFORMS International Conference Hawaii 2001. (2001)

[4] Rusdiansyah, A. and Tsao, De-bi, “In the Search of the Best Visit frequency and Pattern for

the Integrated Inventory and Period Traveling Salesman Problem”, to appear in publication.

[5] Christofides, N. and J.E. Beasley, The Period Routing Problem, Networks, Vol. 14, 237-56

(1984).

[6] Tan,CCR., and J.E. Beasley., “ A Heuristic Algorithm for the Period Vehic le Routing

Problem”, , Omega, Vol. 12, No. 5, pp. 497-504. (1984)

[7] Chao, I-Ming, B.L., Golden, and E. Wasil, “An Improved Heuristic for the Period Vehicle

Routing Problem”, Networks, Vol 26.,pp 25-44 (1995).

[8] Gaudioso, M, and G. Paletta, “A Heuristic for the Periodic Vehicle Routing Problem”,

Transportation Science, Vol. 26, No.2, pp. 86-92. (1992)

[9] Cordeau J.F., M. Gendreau, and G. Laporte x. A Tabu Search Heuristic for Periodic and

Multi-Depot Vehicle Routing Problems. Networks, Vol. 30, 105-119 (1997).

[10] Min H. “The Multiple Vehicle Routing Problem with Simultaneous Delivery and Pickup

Points”, International Journal of Management Science 3:1-14 (19)

[11] Gendreau M, G. Laporte and D. Vigo., “Heuristics for the traveling salesman problem with

pickup and delivery”, Computers and Operations Research 26:699-714 (1999)