A reactive GRASP and path relinking for a combined production–distribution problem

doi:10.1016/j.cor.2006.02.005

Computers & Operations Research

Volume 34, Issue 11, November 2007, Pages 3402-3419

https://doi.org/10.1016/j.cor.2006.02.005 Get rights and content

Abstract

An NP-hard production–distribution problem for one product over a multi-period horizon is investigated. The aim is to minimize total cost taking production setups, inventory levels and distribution into account. An integer linear model is proposed as a compact problem specification but it cannot be solved to optimality for large instances. Instead of using a classical two-phase approach (production planning and then route construction for each day), metaheuristics that simultaneously tackle production and routing decisions are developed: a GRASP (greedy randomized adaptive search procedure) and two improved versions using either a reactive mechanism or a path-relinking process. These algorithms are evaluated on 90 randomly generated instances with 50, 100 and 200 customers and 20 periods. The results confirm the interest of integrating production and distribution decisions, compared to classical two-phase methods. Moreover, reaction and path-relinking give better results than the GRASP alone.

Section snippets

Introduction and literature review

Distribution costs often represent a significant fraction of the actual cost of a finished product. In some sectors like mineral waters, they even dominate production costs. This is why, ideally, any cost reduction effort should encompass production planning and distribution planning. However, in industry, decisions concerning production and distribution to customers or retailers are often made separately, and most companies handle these two levels sequentially. Even when distribution costs are

Problem statement and integer programming model

The problem is defined on a complete weighted and undirected network $G = (N, E, C)$ . N is a set of $n + 1$ nodes indexed from 0 onwards. Node 0 is a plant with a limited fleet F of identical vehicles of capacity W. The set $N^{'} = N ⧹ {0}$ contains n customers. E is the edge set and the weight $C_{ij} = C_{ji}$ on each edge $(i, j)$ is the travelling cost between nodes i and j. See Fig. 1 for an example with 11 customers and 3 days.

The plant manufactures one single product to supply the customers over a planning horizon T

Preliminary GRASP

Greedy randomized adaptive search procedures were introduced in 1989 by Feo and Bard [23], see also [24] for a general presentation of the method. It is based on an iterative randomized sampling of the search space, in which each iteration computes one feasible solution to the problem. Each GRASP iteration consists of two main phases, a construction phase based on a randomized heuristic and a local search phase that improves the trial solution provided by the first phase. After one given number

Reactive GRASP

The GRASP of Section 3 can be made reactive. In a basic GRASP, the size of the RCL $α$ is fixed for all instances and all iterations. However, it is difficult to find the RCL size that gives the best average results. With $α = 1$ , the GRASP becomes a deterministic heuristic and all iterations yield the same solution. If $α$ is too large, well-diversified but low-quality solutions are obtained. The principle of reactive GRASP, proposed for the first time by Prais and Ribeiro [27], is to let the

Path-relinking

Path-relinking (PR) is another possible technique to improve a basic GRASP. It consists of exploring paths between elite solutions found by the GRASP and kept in a small pool. Each path links one initiating solution to one guiding solution. For instance, in Fig. 2, the path from A to B (solid line) does not yield solutions improving A or B, while the path from B to A (dashed line) produces three better solutions.

Ideally, the elite solutions must be well scattered in the solution space and this

Implementation and instances

All algorithms designed in this paper were implemented in Delphi 7 [30] and executed on a 2.8 GHz PC under Windows XP. To the best of our knowledge, no instances are publicly available for our problem. This is why the instances randomly generated in our previous work [31] on simpler heuristics are reused here. There are three sets of 30 instances with 50, 100 and 200 customers respectively, all with $T = 20$ periods.

Some data in the instances depends on the number of customers: production capacity,

Conclusion and future directions

In this paper, different versions of a GRASP improved by a reactive mechanism or by a Path Relinking process have been proposed for solving a combined production–distribution optimization problem. The originality of the approach is to tackle simultaneously production and routing decisions instead of resorting to classical two-phase approaches which are still widely used in practice. The two principal difficulties in the GRASP design were to randomize the construction of a trial solution without

References (32)

P. Toth et al.
The vehicle routing problem
(2002)
M. Gendreau et al.
Stochastic vehicle routing
European Journal of Operational Research
(1996)
M. Christiansen et al.
A method for solving ship routing problems with inventory constraints
Annals of Operations Research
(1998)
M. Dror et al.
Inventory-routing: reduction from an annual to a short-period problem
Naval Research Logistics
(1987)
B.R. Golden et al.
Computerized vehicle routing in the soft drink industry
Operations Research
(1987)
S.C. Graves et al.
Handbooks in operations research and management science, vol. 4: logistics of production and inventory
(1993)
S. Nahmias
Production and operations analysis
(1997)
A.M. Brewer et al.
Handbook of logistics and supply chain management
(2001)
S. Tayur et al.
Quantitative models for supply chain management
(1999)
A.G. De Kok et al.
Handbooks in operation research and management science , vol. 11: supply chain management: design, coordination and operation
(2003)

P. Chandra et al.

Coordination of production and distribution planning

European Journal of Operational Research

(1994)

F. Fumero et al.

Synchronized development of production, inventory, and distribution schedules

Transportation Science

(1999)

S. Selçuk Erengüc et al.

Integrated production/distribution planning in supply chains

An invited review. European Journal of Operational Research

(1999)

D.E. Blumenfeld et al.

Synchronizing production and transportation schedules

Transportation Research

(1991)

V. Jayaraman et al.

Planning and coordination of production and distribution facilities for multiple commodities

European Journal of Operational Research

(2001)

J.F. Bard et al.

A decomposition approach to the inventory routing problem with satellite facilities

Transportation Science

(1998)

Cited by (164)

A green production routing problem for medical nitrous oxide: Model and solution approach
2023, Expert Systems with Applications
The impact of climate change and the global efforts to address it have made environmental considerations increasingly important. Industries and transportation, being major energy consumers, play a significant role in global warming and must reduce their pollutants. This paper presents a bi-objective production routing problem aimed at minimizing the total Greenhouse Gas (GHG) emissions and cost, taking into account real-world constraints and data from a single-plant, multi-distribution center, gaseous-pharmaceutical supply chain with a heterogeneous delivery fleet. The modeling takes into account the GHG emissions from the production process of the product being delivered. A branch and cut method is used in combination with multi-objective fuzzy goal programming to solve the problem. The results show that the proposed model reduces total costs while also reducing GHG emissions compared to the current method used in the case study.
Designing a multi-period dynamic electric vehicle production-routing problem in a supply chain considering energy consumption
2023, Journal of Cleaner Production
The coordinated decision-making approach for considering sequential activities of the supply chain results in additional benefits by optimizing production, inventory, and distribution operations. Accordingly, this paper proposes a mixed integer linear mathematical model to optimize a multi-period production routing problem utilizing electric vehicles. The proposed model optimizes the total cost associated with fixed and variable production, holding inventory, and routing, including the fixed cost of utilizing electric vehicles and travel time. However, mileage limitation is one of the main restrictions of utilizing electric vehicles in performing deliveries which is strongly affected by the consumed energy. Although optimization of the routes of vehicles can facilitate using them, considering the variation of travel speed network links during different times of the day because of traffic conditions can obviously affect the required energy to perform the assigned deliveries. To the best of our knowledge, this paper is the ﬁrst to study simultaneous multi-period dynamic production routing problems using a set of heterogenous electric vehicles whose travel time of links can vary by dividing each production period into several hourly time intervals to capture different traffic conditions. Finally, a series of capable and hybrid metaheuristic algorithms are designed and implemented to solve this problem in a real-case dimension, and all proposed algorithms are compared.
A Memetic Algorithm for the multi-product Production Routing Problem
2023, Computers and Industrial Engineering
This article addresses the Production Routing Problem (PRP), which consists of determining, in an integrated way, production and inventory planning, and vehicle routing to minimize the costs involved. In the problem, a plant is responsible for producing several types of products to meet the known demand of a set of customers using a homogeneous fleet of vehicles over the planning horizon. In the literature, evolutionary approaches have not been explored in depth for the PRP, specifically for the problem with multiple products. Thus, this work mitigates this gap, presenting a novel Memetic Algorithm and testing its effectiveness on randomly generated sets of instances, comparing the results obtained with a commercial optimization solver. In our solution approach, several classic operators from the literature were implemented. Furthermore, we propose four novel genetic operators. In addition, we evaluated the proposed method’s performance in classical instances of literature considering a single item. The computational experiments were carried out to assess the impact of the numerous parameter combinations involving the metaheuristic, and, from statistical analyses, we evidence the proposed technique’s robustness. Computational experiments showed that our proposed method outperforms the commercial solver Gurobi in determining feasibly high-quality solutions, mainly on large instances for the PRP with multiple items.
The leader multipurpose shopping location problem
2022, European Journal of Operational Research
This paper extends the follower's retail store location problem of Marianov et al. (2018) to include the leader's decisions. The leader locates its stores knowing that a follower will enter the market later offering a different product. Both maximize their markets given that customers can purchase none, one or two non-essential products on the same trip. The paper determines the best locations for a first and a second entrants through exact and approximated procedures. It turns out that, by locating with foresight, a first entrant can increase the total business in an area for himself and subsequent entrants. We solve the binary programming bi-level resulting problem for small instances by adapting an ad-hoc procedure. Furthermore, a new bi-level reactive GRASP procedure finds solutions for instances of up to 100 nodes in under 3,600 s of CPU time.
Formulation and exact algorithms for electric vehicle production routing problem
2022, Expert Systems with Applications
Advanced decision-making models have been recently developed to integrate various aspects of a supply chain, i.e., production, distribution, shipping, and routing. These have resulted in higher productivity and significant cost saving. On the other side, regulations, and incentives to operate Electric Vehicles (EVs) are growing to address the environmental impacts of a supply chain. In this study, we present an Electric Vehicle Production Routing Problem (EVPRP) to achieve optimal decisions. In the proposed problem the limitation of battery capacity and charging facilities is incorporated. In addition, to address the issue of long charging, the option of partial charging is considered using both Heterogeneous (HT) and Homogeneous (HM) fleets. We propose a mixed-integer linear programming model for the EVPRP, which is mathematically validated by solving (via CPLEX) the new instances generated compatible with the EVPRP. Due to the NP-hardness of the EVPRP model, which cannot solve large-scale instances by a commercial solver, we develop two types of exact algorithms named, Logic-Based Benders Decomposition (LBBD) algorithms. The first one is based on each vehicle in each period ( ${LBBD}_{vt}$ ), and the second algorithm is applied for each period ( ${LBBD}_{t}$ ). The performance of the proposed model and LBBD algorithms is validated through the computational experiments on the HM and HT EVPRP data sets. The computational results show that the proposed exact algorithms clearly outperform the MIP formulation solved by Cplex as well as demonstrate the efficiency of both algorithms in finding high-quality solutions.
Integrated production and inventory routing planning of oxygen supply chains
2022, Chemical Engineering Research and Design
In this work, we address a production and inventory routing problem for a liquid oxygen supply chain comprising production facilities, distribution network, and distribution resources. The key decisions of the problem involve production levels of production plants, delivery schedule and routing through heterogeneous vehicles, and inventory strategies for national stock-out prevention. Due to the problem complexity, we propose a two-level hybrid solution approach that solves the problem using both exact and metaheuristic methods. At the upper level, we develop a mixed-integer linear programming (MILP) model that determines production and inventory decisions and customer allocation. In the lower level, the original problem is reduced to several multi-trip heterogeneous vehicle routing problems by fixing the optimal production, inventory, and allocation decisions and clustering customers. A well-recognised metaheuristic, guided local search method, is adapted to solve the low-level routing problems. A real-world case study in the UK illustrates the applicability and effectiveness of the proposed optimisation framework.

View all citing articles on Scopus

View full text

A reactive GRASP and path relinking for a combined production–distribution problem

Abstract

Section snippets

Introduction and literature review

Problem statement and integer programming model

Preliminary GRASP

Reactive GRASP

Path-relinking

Implementation and instances

Conclusion and future directions

The vehicle routing problem

Stochastic vehicle routing

European Journal of Operational Research

A method for solving ship routing problems with inventory constraints

Annals of Operations Research

Inventory-routing: reduction from an annual to a short-period problem

Naval Research Logistics

Computerized vehicle routing in the soft drink industry

Operations Research

Handbooks in operations research and management science, vol. 4: logistics of production and inventory

Production and operations analysis

Handbook of logistics and supply chain management

Quantitative models for supply chain management

Handbooks in operation research and management science , vol. 11: supply chain management: design, coordination and operation

Coordination of production and distribution planning

European Journal of Operational Research

Synchronized development of production, inventory, and distribution schedules

Transportation Science

Integrated production/distribution planning in supply chains

An invited review. European Journal of Operational Research

Synchronizing production and transportation schedules

Transportation Research

Planning and coordination of production and distribution facilities for multiple commodities

European Journal of Operational Research

A decomposition approach to the inventory routing problem with satellite facilities

Transportation Science