As fresh product e-commerce experiences exponential expansion, the delivery of fresh products which are perishable is becoming a large part of road freight transportation. Transporting perishable products is a challenging task as it is difficult to preserve their nutritional value and freshness. To keep the freshness of such products in delivery, efficient transportation is critical. Besides, customers nowadays attach more importance to service flexibility, which contributes to customer satisfaction and is highly valued by suppliers. However, the service flexibility was seldom addressed previously in the delivery of fresh products. In this paper, we study a vehicle routing problem faced by a supplier who delivers perishable products to customers. We consider the service flexibility of the supplier who offers different delivery modes associated with differentiated time windows to customers. The supplier aims to maximize both its profit and customer satisfaction, where the customer satisfaction is measured by the weighted average quality loss of perishable products during delivery. This bi-objective vehicle routing problem with different customer priorities and delivery time windows is structured as a bi-objective mixed-integer linear programming model. To obtain the Pareto frontier of the model, an adaptive large neighborhood search (ALNS) algorithm based on the$\varepsilon $-constraint method and a multi-objective ALNS algorithm are developed with several improvement strategies proposed. The computational results conducted on modified Solomon’s instances validate the model and prove the efficiency of the algorithms. Sensitivity analysis of the problem and the algorithms provide some managerial insights.

We study a realistic Bi-objective Multimodal Transportation Planning Problem (BMTPP) faced by logistics companies when trying to obtain cost advantages and improve the customer satisfaction in a competitive market. The two objectives considered are: the minimization of total transportation cost and the maximization of service quality. Given a set of transportation orders described by an origin, a destination and a time window, solving BMTPP involves determining the delivery path for each order in a capacitated network as well as selecting the carrier with the best service quality for each edge of the path. The BMTPP is formulated as a novel bi-objective mixed integer linear programming model and an iterative$\epsilon $-constraint method is applied to solve it. As the NP-hardness of the single-objective problems derived from BMTPP, a Lagrangian Relaxation (LR) heuristic which can not only provide a near-optimal solution but also a lower bound for each of the single-objective problems is developed. 100 randomly generated instances are tested and the computational results demonstrate the effectiveness of the heuristic in obtaining a tight lower bound and a high-quality near-optimal solution for the derived single-objective problem. Various performance indicators show the high-quality of the Pareto front of the bi-objective problem obtained by the heuristic. We also provide a case study for the proposed LR heuristic in a logistics network in China.

Transportation service procurement is often realized by an auction. With the rolling horizon planning concept adopted in logistics, carriers usually plan their transportation operations of several periods (days) in advance. This implies that carriers must consider multiple periods when participating in combinatorial auctions organized by shippers. Since transportation requests in future cannot be foreseen, carriers must consider request uncertainty in such auctions. In this paper, we consider a carrier’s bid generation problem appeared in a multi-round combinatorial auction for truckload transportation service procurement with the consideration of multiple periods and request uncertainty. The problem is to maximize the total expected net profit of the carrier in a planning horizon of multiple periods by optimally determining the transportation requests to bid, the period to serve each request, and the routes to serve all requests including the carrier’s reserved requests. This problem is hard to solve because of its stochastic nature. By adopting the scenario approach of stochastic optimization, a mixed integer linear programming model is formulated for the problem. A Benders decomposition approach is then proposed to solve the model, with Pareto-optimal cuts to accelerate its solution process. The performance of the approach is evaluated by numerical experiments on randomly generated instances. The computational results demonstrate that the Bender decomposition approach is much more efficient than CPLEX solver in solving large instances of the problem. In addition, the value of considering uncertain requests and multi-period in the bid generation is evaluated.

We study a new competitive multi-facility location and quality design problem in a continuous space. The facility location and quality design are considered together because of their interdependence. Especially, new entrant facilities compete for customer demands with existing ones and the latter’s reactions are taken into account. The goal is to maximize the profit of all new entrant facilities by optimally determining their locations and qualities. For this problem, a probabilistic Huff-like gravity model is adopted to analyze the market share to be captured by new and existing facilities, and then a mathematical programming model is provided based on the market share analysis. Since it is shown to be strongly NP-hard, a new iterative solution framework is first proposed to solve it, where at each iteration, new configurations of facility locations are firstly generated, and then the quality decisions of all facilities are modelled as a competitive decision process by a non-cooperative game. The best qualities for new and existing facilities are determined by their Nash equilibrium. Finally, optimal or near-optimal solutions are calculated. Then based on the proposed solution framework, a particle swarm optimization-based approach is developed. Computational results for randomly generated instances indicate that the devised algorithm is able to find suitable locations and qualities of newly entering facilities in a competitive environment and outperforms favorably a genetic algorithm-based approach.

Retailers with short lifetime products in stock always face a problem of whether new products should be ordered when on-hand products partially decay and how to deal with the old products if a new batch is ordered. In this article, we consider the sales of a perishable product with a fixed short lifetime in two shelves, where new items of the product in a regular shelf are sold in a preset normal price, and old items in a markdown (discount) shelf are sold in a discounted price. We study the problem of the joint ordering of new items and pricing of old items and propose a joint ordering and markdown policy when the demand of the product depends on its price, and freshness as well as unsatisfied demand is lost. First, we formulate a one-period model, in which the present shelf ages of items in the two shelves are considered and use the Karush–Kuhn–Tucker condition to analytically obtain the optimal solution of the joint ordering and markdown problem. Second, numerical experiments are conducted to evaluate the performance of the two-shelf policy when the optimal solution of the one-period model is applied to the multiperiod problem in the form of a myopic policy. The results show that the proposed two-shelf joint ordering and markdown policy for perishable products performs better than the traditional one-shelf policy.Note to Practitioners—In this article, we develop a joint ordering and markdown policy for perishable products deployed on two shelves: a regular shelf for fresh products and a markdown shelf for less fresh products. Although the closed-form policy is obtained for the one-period situation with deterministic demand, it is not difficult to extend it to the multiperiod case with random demand. This article not only reveals the underlying reason of employing both regular shelf and markdown shelf in the practice of retailing management for perishable products but also proposes an easy-to-implement ordering and markdown policy, which will bring higher profit than the traditional one-shelf policy and will improve the performance of managing a perishable products retailing system.

International audience

International audience

International audience

International audience

Inventory record inaccuracy has significant negative impacts on the performance of inventory management. We investigate a robust replenishment problem for an inventory system under inventory record inaccuracy caused by invisible stock loss, with the objective of minimizing the sum of the inventory holding cost, the backorder cost, and the materials transportation cost. First, we develop a recursive algorithm to estimate the probability distribution of the physical inventory levels. Based on this probability distribution, a robust myopic reorder-time/order-quantity (RTQ) policy is designed, which determines the robust reorder time and the robust replenishment quantity. Theoretical analysis and numerical experiments reveal some managerial insights of the proposed RTQ policy and the classical (r, Q), (s, S), and (R, S) policies: 1) if there exist invisible stock loss and inaccurate inventory record, the inventory system will be trapped into the zero-service state (i.e., the inventory level becomes less than or equal to zero with probability one) in finite time under the classical policies and 2) if the probability distribution of inventory record error is known exactly, the RTQ policy prevents the inventory system from being trapped into the zero-service state and maintains a high service level, even if we do not make any audit of its physical inventory level.

Crude oil transportation is a central logistics operation in petrochemical industry because its cost represents a significant part in the cost of petrochemical products. In this paper, we consider the transportation by tankers or trucks. We show that under some realistic assumptions, this problem can be transformed into a single item lot sizing problem with limited production and inventory capacities. We develop a strongly polynomial dynamic programming algorithm to solve it. The problem of crude oil transportation is very difficult. There are few efficient methods in this domain. In the model considered in this paper, crude oil is directly shipped from a supplier port tonclient ports to satisfy customer demands overTfuture periods. The supplier port disposes a fleet of identical tankers with limited capacity. The inventory capacities of customers are limited and time-varying. The backlogging is admitted. The objective is to find an optimal shipment plan minimizing the total cost over theT-period horizon. When the number of tankers is unlimited and customer demands are independent, shipment plans of different customers become independent. This problem can be considered asnindependent problems. Each of them can be transformed into a single item lot sizing problem with limited production and inventory capacities, where tanker capacity corresponds to production capacity in classical lot sizing models. The main contributions of this paper are: 1) transformation of a transportation planning problem into a lot-sizing problem; 2) an O(T3) algorithm is proposed to solve it; and 3) the results can also be applied to terrestrial transportation with direct deliveries.

This paper considers the infinite horizon inventory routing problem for one-warehouse multi-retailer distribution systems. We focus on developing an analytic approach for evaluating the effectiveness of direct shipping strategy where each vehicle serves only one retailer in one delivery at its optimal replenishment rate. Explicit formula is obtained in terms of a few of easily measurable parameters. The formula allows the effectiveness of direct shipping strategy to be evaluated quickly using even a hand calculator. We demonstrate that the effectiveness of direct shipping is at least the square root of the smallest utilization ratio of vehicle capacity. This implies that direct shipping is 100% (respectively 94.86%) effective whenever the smallest utilization ratio is 100% (respectively 90%). This insight can help a firm answer questions such as: under what conditions does direct shipping perform well, and why? How well does direct shipping perform in a specific situation.

We consider the inventory-routing problem for a three-level distribution system consisting of a single outside vendor, a single warehouse and many geographically dispersed retailers. Each retailer faces external demands for a single item which arise at a deterministic, retailer specific rate. Inventory holding cost is charged at both the warehouse and the retailers. All shipments are delivered by a fleet of homogeneous vehicles of limited capacity. We develop a lower bound on the long run average cost over any feasible policies. We use this lower bound to show that an effective strategy, in which all shipments are delivered from the vendor to the retailers not to pass the warehouse, is at least radic2 asymptotic optimal, and with a high probability, the strategy has a higher asymptotic optimality than the strategy to pass the warehouse. Particularly, if the probability distribution of the retailer demand rates allows for perfect packing, then the strategy is almost surely 100% asymptotic optimal and better than the strategy to pass the warehouse. Our results also show that the strategy not to pass the warehouse as well as the strategy to pass the warehouse would not work very well in three-level distribution systems with limited number of retailers or with many retailers but the perfect packing ratio allowed by the retailer demand rates is small. Further we provide a numerical example to show that in some conditions the strategy to pass the warehouse is better than the strategy not to pass the warehouse. We then can conclude that a hybrid strategy, i.e., combing the strategy not to pass the warehouse with the strategy to pass the warehouse, should be used in three-level distribution systems with limited number of retailers or with many retailers but the perfect packing ratio allowed by the retailer demand rates is small.

This paper presents our work on modeling and performance analysis of inventory systems using batch deterministic and stochastic Petri nets (BDSPNs). It addresses issues frequently raised by industrial companies, but did not receive enough attention by the Petri nets (PNs) community in spite of its important role in the study of discrete event systems. The BDSPN is a new class of PNs capable of describing the synchronization of discrete and batch token flows in discrete batch processes. Such processes appear in inventory systems or more general supply chains where materials are purchased in finite discrete quantities (batches of different sizes), and many operations such as inventory replenishment and customer order fulfillment are usually performed in a batch way because of the batch nature of customer orders and/or in order to take advantages of the economies of scale. In this paper, the BDSPN model is formally introduced, and its conflict resolutions of transitions and batch firing indexes are addressed. The model is then applied to the modeling and performance evaluation of various inventory systems. Analytic performance evaluation techniques are developed for the model with illustrative applications to the inventory systems. Our study shows that the model is powerful for both modeling and performance evaluation of the systems.

Batch deterministic and stochastic Petri nets are introduced as a tool for modeling and performance evaluation of supply chains. The new model is developed by enhancing deterministic and stochastic Petri nets (DSPNs) with batch places and batch tokens. By incorporating stochastic Petri nets (SPNs) with the batch features, inhibitor arcs, and marking-dependent weights, operational policies of supply chains such as inventory policies can be easily described in the model. Methods for structural and performance analysis of the model are developed by extending existing ones for DSPNs. As applications, an inventory system and an industrial supply chain are modeled and their performances are evaluated analytically and by simulation, respectively, using this BSPN model. The applications demonstrate that our model and associated methods can solve some important supply chain modeling and analysis issues. Note to Practitioners-This paper was motivated by the problem of performance analysis and optimization of supply chains but it also applies to other discrete event systems where materials are processed in finite discrete quantities (batches) and operations are performed in a batch way because of batch inputs and/or in order to take advantages of the economies of scale. Existing Petri net modeling and analysis tools for such systems ignore their batch features, making their modeling complicated. This paper suggests a new model called batch deterministic and stochastic Petri nets (BDSPNs) by enhancing deterministic and stochastic Petri nets with batch places and batch tokens. Methods for structural and performance analysis of the model are developed. We then show how an inventory system and a real-life supply chain can be modeled and their performances can be evaluated analytically and by simulation respectively based on the model. The model and associated analysis methods therefore provide a promising tool for modeling and performance evaluation of supply chains.

International audience

Pressed by market globalization and concomitant competition, more and more manufacturers are relying on their suppliers to provide raw materials and component parts so as to focus on their core competence. As a result, the coordination of activities across a network of suppliers becomes critical to quickly respond to dynamic market conditions. In this paper, a novel framework combining mathematical optimization and the contract net protocol is presented for make-to-order supply network coordination. Interactions among organizations are modeled by a set of interorganizational precedence constraints and the objective is to achieve the organizations' individual and shared goals of fast product delivery and low inventory. These interorganizational constraints are relaxed by using a set of interorganizational prices that represent marginal costs per unit time for the violation of such constraints. The overall problem is thus decomposed into organizational subproblems, where individual organizations schedule their activities based on their internal situations and interorganizational prices. Coordination is achieved through an iterative price-updating process carried out in a distributed and asynchronous manner. With prices dynamically updated and schedules adjusted, this approach coordinates activities to fulfill existing commitments while maintaining agility to take on new orders. Numerical testing results show that interorganizational prices converge and prices may change as new orders arrive to reflect the new pressure on deliveries.

Batch deterministic and stochastic Petri nets are developed as a new tool for modeling and performance evaluation of supply chain. It is derived by enhancing deterministic and stochastic Petri nets. with batch places and batch tokens. Batch tokens, which have sizes and reside in batch places, are used to describe the information flow of a supply chain, while discrete tokens residing in discrete places are used to describe the material flow and the financial flow. By incorporating stochastic Petri nets with the batch features, inhibitor arcs, and marking-dependent weights, operational policies of a supply chain can be easily described in the model. A real-life supply chain is modeled by applying this tool and its performance is evaluated and optimized by simulation.

A time window based approach is developed for job shop scheduling problems to minimize the weighted earliness and tardiness cost. With the time windows provided by Lagrangian relaxation within which parts are processed to minimize the cost and an effective algorithm to find a feasible schedule within or approximately within the windows, the approach can generate schedules better than those generated by the Lagrangian relaxation approach for large problems in a similar computation time. This demonstrates that our approach can be used to solve practical scheduling problems with an improved performance.

Manufacturing enterprise automation was focused on factory level where scheduling is a key issue in the past. As more and more companies are relying on their business partners or suppliers, the coordination of activities through the chain of suppliers becomes critical to quickly respond to changing market conditions. The rapid growth of information technology is now opening up a unique opportunity for companies to coordinate with their customers and suppliers to further improve their responsiveness. Effective approaches for coordination, however, have to be developed to grab the opportunity. In the paper, existing approaches for scheduling and coordination are summarized, important issues for coordination such as architecture, solution concept and scalability are discussed, and a price-based approach is presented for supply chain coordination. In the approach, each organization makes its own decision based on the prices associated with inter-organization constraints, and the coordination among organizations is performed in a distributed and asynchronous way with prices iteratively adjusted by related organizations. The coordination approach is scalable if the prices are constantly adjusted to dynamically adapt to changing conditions and the price adjustment process is stable.

In this paper, arc-timed Petri nets are used to model controlled real-time discrete event systems, and the control synthesis problem that designs a controller for a system to satisfy its given closed-loop behavior specification is addressed. For the problem with the closed-loop behavior specified by a state predicate, real-time control-invariant predicates are introduced, and a fixpoint algorithm to compute the unique extremal control-invariant subpredicate of a given predicate, key to the control synthesis, is presented. For the problem with the behavior specified by a labeled arc-timed Petri net, it is shown that the control synthesis problem can be transformed into one that synthesizes a controller for an induced arc-timed Petri net with a state predicate specification. The problem can then be solved by using the fixpoint algorithm as well. The algorithm involves conjunction and disjunction operations of polyhedral sets and can be algorithmically implemented, making automatic synthesis of controllers for real-time discrete event systems possible.

Genetic algorithms have been applied to the scheduling of job shops-a class of very complicated combinatorial optimization problems. Among these algorithms for job shops, a common assumption is that the routes that jobs visit machines are fixed, this is not true for flexible job shops such as flexible manufacturing systems, where jobs have machine route flexibility. The paper presents a new genetic algorithm to solve the flexible job-shop scheduling problem with makespan criterion. The representation of solutions for the problem by chromosomes consists of two parts. The first part defines the routing policy and the second part the sequence of the operations on each machine. Genetic operators are introduced and used in the reproduction process of the algorithm. Numerical experiments show that our algorithm can find out high-quality schedules.

This paper proposes a model and a related algorithm for generating optimal cyclic schedules of hoist moves with time window constraints in a printed circuit board (PCB) electroplating facility. The algorithm is based on the branch and bound approach and requires the solution of a specific class of linear programming problems (LPP). These LPP are equivalent to the problems of the cycle time evaluation in bi-valued graphs. Computational experience is presented to compare the results obtained using this new algorithm with the ones proposed in the literature.

Concerns the use of Lagrangean relaxation for complex scheduling problems. The technique has been used to obtain near-optimal solutions for single machine and parallel machine problems. It consists of relaxing capacity constraints using Lagrange multipliers. The relaxed problem can be decomposed into independent job level subproblems. Luh et al. (1990, 1991) extended the technique to general job shop scheduling by introducing additional Lagrangean multipliers to relax precedence constraints, so that each job level relaxed subproblem can be further decomposed into a set of operation level subproblems which can easily be solved by enumeration. Unfortunately, the operation level subproblems exhibit solution oscillation from iteration to iteration and, in many cases, prevent convergence. Although several methods to prevent oscillation have been proposed, none is satisfactory. We propose an efficient pseudo-polynomial time dynamic programming algorithm. We show that, by extending the technique to job shop scheduling problems, the relaxation of the precedence constraints becomes unnecessary, and thus the oscillation problem vanishes. This algorithm significantly improves the efficiency of the Lagrangean relaxation approach to job-shop scheduling, and makes it possible to optimize "min-max" criteria by Lagrangean relaxation. These criteria have been neglected in the Lagrangean relaxation literature due to their indecomposability. Computational results are given to demonstrate the improvements due to this algorithm.

Lagrangian relaxation consists of relaxing capacity constraints using Lagrangian multipliers and of decomposing the problem into job level subproblems. In the literature, when job shop scheduling problems are considered, these subproblems are further decomposed into operation level subproblems by relaxing precedence constraints. Unfortunately, this results in solution oscillation and often prevents convergence of the algorithm. Although several methods have been proposed to avoid solution oscillation, none of them is really satisfactory. In this paper, we propose an efficient pseudopolynomial time dynamic programming algorithm to solve relaxed job level subproblems. This makes the relaxation of precedence constraints unnecessary. The solution oscillation can then be avoided. This algorithm also results in a much more efficient Lagrangian relaxation approach to job-shop scheduling problems. Computational results on randomly generated problems are given to demonstrate the efficiency of the algorithm.