A reactive GRASP and path relinking for a combined production–distribution problem
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 . N is a set of nodes indexed from 0 onwards. Node 0 is a plant with a limited fleet F of identical vehicles of capacity W. The set contains n customers. E is the edge set and the weight on each edge 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 , 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 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)
- et al.
The vehicle routing problem
(2002) - et al.
Stochastic vehicle routing
European Journal of Operational Research
(1996) - et al.
A method for solving ship routing problems with inventory constraints
Annals of Operations Research
(1998) - et al.
Inventory-routing: reduction from an annual to a short-period problem
Naval Research Logistics
(1987) - et al.
Computerized vehicle routing in the soft drink industry
Operations Research
(1987) - et al.
Handbooks in operations research and management science, vol. 4: logistics of production and inventory
(1993) Production and operations analysis
(1997)- et al.
Handbook of logistics and supply chain management
(2001) - et al.
Quantitative models for supply chain management
(1999) - et al.
Handbooks in operation research and management science , vol. 11: supply chain management: design, coordination and operation
(2003)
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
Cited by (164)
A green production routing problem for medical nitrous oxide: Model and solution approach
2023, Expert Systems with ApplicationsDesigning a multi-period dynamic electric vehicle production-routing problem in a supply chain considering energy consumption
2023, Journal of Cleaner ProductionA Memetic Algorithm for the multi-product Production Routing Problem
2023, Computers and Industrial EngineeringThe leader multipurpose shopping location problem
2022, European Journal of Operational ResearchFormulation and exact algorithms for electric vehicle production routing problem
2022, Expert Systems with ApplicationsIntegrated production and inventory routing planning of oxygen supply chains
2022, Chemical Engineering Research and Design