Integrated production and distribution scheduling with lifespan constraints

We consider an integrated production and distribution scheduling problem in a make-to-order business scenario. A product with a short lifespan (e.g., perishable or seasonal) is produced at a single production facility with a limited production rate. This means that the product expires in a constant time after its production is finished. Orders are received from a set of geographically dispersed customers, where a demand for the product and a time window for the delivery is associated with each customer for the planning period. A single vehicle with non-negligible traveling times between the locations is responsible for the deliveries. Due to the limited production and distribution resources, possibly not all customers may be supplied within their time windows or the lifespan. The problem consists in finding a selection of customers to be supplied such that the total satisfied demand is maximized. We extend the work by Armstrong et al. (Annals of Operations Research 159(1):395–414, 2008) on the problem for fixed delivery sequences by pointing out an error in their branch and bound algorithm and presenting a corrected variant. Furthermore, we introduce model extensions for handling delays of the production start as well as for variable production and distribution sequences. Efficient heuristic solution algorithms and computational results for randomly generated instances are presented.     

A greedy look-ahead heuristic for the vehicle routing problem with time windows

In this paper we consider the problem of physically distributing finished goods from a central facility to geographically dispersed customers, which pose daily demands for items produced in the facility and act as sales points for consumers. The management of the facility is responsible for satisfying all demand, and promises deliveries to the customers within fixed time intervals that represent the earliest and latest times during the day that a delivery can take place. We formulate a comprehensive mathematical model to capture all aspects of the problem, and incorporate in the model all critical practical concerns such as vehicle capacity, delivery time intervals and all relevant costs. The model, which is a case of the vehicle routing problem with time windows, is solved using a new heuristic technique. Our solution method, which is based upon Atkinson's greedy look-ahead heuristic, enhances traditional vehicle routing approaches, and provides surprisingly good performance results with respect to a set of standard test problems from the literature. The approach is used to determine the vehicle fleet size and the daily route of each vehicle in an industrial example from the food industry. This actual problem, with approximately two thousand customers, is presented and solved by our heuristic, using an interface to a Geographical Information System to determine inter-customer and depot–customer distances. The results indicate that the method is well suited for determining the required number of vehicles and the delivery schedules on a daily basis, in real life applications.     

A truck and drones model for last-mile delivery: A mathematical model and heuristic approach

We present a mathematical formulation and a heuristic solution approach for the optimal planning of delivery routes in a multi-modal system combining truck and Unmanned Aerial Vehicle (UAV) operations. In this system, truck and UAV operations are synchronized, i.e., one or more UAVs travel on a truck, which serves as a mobile depot. Deliveries can be made by both UAVs and the truck. While the truck follows a multi-stop route, each UAV delivers a single shipment per dispatch. The presented optimization model minimizes the waiting time of customers in the system. The model determines the optimal allocation of customers to truck and UAVs, the optimal route sequence of the truck, and the optimal launch and reconvene locations of the UAVs along the truck route. We formulate the problem as a Mixed-Integer Linear Programming (MILP) model and conduct a bound analysis to gauge the maximum potential of the proposed system to reduce customer waiting time compared to a traditional truck-only delivery system. To be able to solve real-world problem size instances, we propose an efficient Truck and Drone Routing Algorithm (TDRA). The solution quality and computational performance of the mathematical model and the TDRA are compared together and with the truck-only model based on a variety of problem instances. Further, we apply the TDRA to a real-world case study for e-commerce delivery in São Paulo, Brazil. Our numerical results suggest significant reductions in customer waiting time to be gained from the proposed multi-modal delivery model.     

Optimal and heuristic algorithms for multiproduct uncapacitated facility location

We consider a generalization of the classic uncapacitated facility location problem (UFLP) in which customers require multiple products. We call this the multiproduct uncapacitated facility location problem (MUFLP). In MUFLP, in addition to a fixed cost for opening a facility, a fixed cost is incurred for each product that a facility is equipped to handle. Also, an assignment cost is incurred for satisfying a customer's requirement for a particular product at a chosen facility. We describe a branch-and-bound algorithm for MUFLP. Lower bounds are obtained by solving a UFLP subproblem for each product using a dual ascent routine. We also describe a heuristic branch-and-bound procedure in which the solutions to the subproblems at a given node might not generate a true lower bound. To generate a feasible solution, a ‘superposition’ heuristic based on solving UFLP subproblems for each product, as well as a ‘drop’ heuristic that eliminates facilities and equipment from the solution in a step-by-step manner, are given. Computational results are reported.     

Real-time split-delivery pickup and delivery time window problems with transfers

In this research we present the design and implementation of heuristics for solving split-delivery pickup and delivery time window problems with transfer (SDPDTWP) of shipments between vehicles for both static and real-time data sets. In the SDPDTWP each shipment is constrained with the earliest possible pickup time from the origin and the latest acceptable delivery time to a destination. Split-deliveries occur when two or more vehicles service the same origin or destination. The proposed heuristics were applied to both static and real-time data sets. The heuristics computed a solution, in a few seconds, for a static problem from the literature, achieving an improvement of 60% in distance in comparison to the published solution. In the real-time SDPDTWP problems, requests for pickup and delivery of a package, breakdown of a truck or insertion of a truck can occur after the vehicle has left the origin and is enroute to service the customers. Thirty data sets, each consisting of one to seven real-time customer or truck events, were used to test the efficiency of the heuristics. The heuristics obtained solutions to real-time data sets in under five seconds of CPU time.      

The scheduling of deliveries in a production-distribution system with multiple buyers

In a real production and distribution business environment with one supplier and multiple heterogeneous buyers, the differences in buyers’ ordering cycles have influence on production arrangements. Consequently, the average inventory level (AIL) at the supplier’s end is affected by both the production policy and the ordering policy, typically by the scheduling of deliveries. Consequently, the average inventory holding cost is most deeply affected. In this paper, it is proposed that the scheduling of deliveries be formulated as a decision problem to determine the time point at which deliveries are made to buyers in order to minimize the supplier’s average inventory. A formulation of the average inventory level (AIL) in a production cycle at the supplier’s end using a lot-for-lot policy is developed. Under the lot-for-lot policy, the scheduling of deliveries (SP) is formulated as a nonlinear programming model used to determine the first delivery point for each buyer with an objective to minimize the sum of the product of the individual demand quantity and the first delivery time for each buyer. Thus, the SP model determines not only the sequence of the first deliveries to individual buyers, but also the time when the deliveries are made. An iterative heuristic procedure (IHP) is developed to solve the SP model assuming a given sequence of buyers. Six sequence rules are considered and evaluated via simulation.     

A truck scheduling problem arising in intermodal container transportation

We address a truck scheduling problem that arises in intermodal container transportation, where containers need to be transported between customers (shippers or receivers) and container terminals (rail or maritime) and vice versa. The transportation requests are handled by a trucking company which operates several depots and a fleet of homogeneous trucks that must be routed and scheduled to minimize the total truck operating time under hard time window constraints imposed by the customers and terminals. Empty containers are considered as transportation resources and are provided by the trucking company for freight transportation. The truck scheduling problem at hand is formulated as Full-Truckload Pickup and Delivery Problem with Time Windows (FTPDPTW) and is solved by a 2-stage heuristic solution approach. This solution method was specially designed for the truck scheduling problem but can be applied to other problems as well. We assess the quality of our solution approach on several computational experiments.     

Algorithms for a Facility Location Problem with Stochastic Customer Demand and Immobile Servers

This paper studies a facility location problem with stochastic customer demand and immobile servers. Motivated by applications to locating bank automated teller machines (ATMs) or Internet mirror sites, these models are developed for situations in which immobile service facilities are congested by stochastic demand originating from nearby customer locations. Customers are assumed to visit the closest open facility. The objective of this problem is to minimize customers' total traveling cost and waiting cost. In addition, there is a restriction on the number of facilities that may be opened and an upper bound on the allowable expected waiting time at a facility. Three heuristic algorithms are developed, including a greedy-dropping procedure, a tabu search approach and an -optimal branch-and-bound method. These methods are compared computationally on a bank location data set from Amherst, New York.     

自由作业的供应链排序研究

研究一类集成工件加工和发送的供应链排序模型,即研究如何安排工件在自由作业机器上加工,把加工完毕的工件分批发送给下游客户,使得含生产排序费用和发送费用的目标函数最优.这里,分别取工件最大送到时间和平均送到时间为生产排序费用;而发送费用是由固定费用和与运输路径有关的变化费用组成.利用排序理论和动态规划方法,构造了自由作业供应链排序问题的多项式时间近似算法,并分析算法的性能比.     

Blow-Up Phenomena for Some Pseudo-Parabolic Equations with Nonlocal Term

We investigate the initial boundary value problem of some semilinear pseudo-parabolic equations with Newtonian nonlocal term. We establish a lower bound for the blow-up time if blow-up does occur. Also both the upper bound for $T$ and blow up rate of the solution are given when $J(u_0)<0$. Moreover, we establish the blow up result for arbitrary initial energy and the upper bound for $T$. As a product, we refine the lifespan when $J(u_0)<0.$     

An iterative three-component heuristic for the team orienteering problem with time windows

This paper studies the team orienteering problem with time windows, the aim of which is to maximize the total profit collected by visiting a set of customers with a limited number of vehicles. Each customer has a profit, a service time and a time window. A service provided to any customer must begin in his or her time window. We propose an iterative framework incorporating three components to solve this problem. The first two components are a local search procedure and a simulated annealing procedure. They explore the solution space and discover a set of routes. The third component recombines the routes to identify high quality solutions. Our computational results indicate that this heuristic outperforms the existing approaches in the literature in average performance by at least 0.41%. In addition, 35 new best solutions are found.     

Production scheduling with supply and delivery considerations to minimize the makespan

In this paper we study a scheduling model that simultaneously considers production scheduling, material supply, and product delivery. One vehicle with limited loading capacity transports unprocessed jobs from the supplier’s warehouse to the factory in a fixed travelling time. Another capacitated vehicle travels between the factory and the customer to deliver finished jobs to the customer. The objective is to minimize the arrival time of the last delivered job to the customer. We show that the problem is NP-hard in the strong sense, and propose an O(n) time heuristic with a tight performance bound of 2. We identify some polynomially solvable cases of the problem, and develop heuristics with better performance bounds for some special cases of the problem. Computational results show that all the heuristics are effective in producing optimal or near-optimal solutions quickly.     

Supply chain models for an assembly system with preprocessing of raw materials

In this paper, we investigate the material procurement and delivery policy in a production system where raw materials enter into the assembly line from two different flow channels. The system encompasses batch production process in which the finished product demand is approximately constant for an infinite planning horizon. Two distinct types of raw materials are passed through the assembly line before to convert them into the finished product. Of the two types of raw materials, one type requires preprocessing inside the facility before the assembly operation and other group is fed straightway in the assembly line. The conversion factors are assigned to raw materials to quantify the raw material batch size required. To analyze such a system, we formulate a nonlinear cost function to aggregate all the costs of the inventories, ordering, shipping and deliveries. An algorithm using the branch and bound concept is provided to find the best integer values of the optimal solutions. The result shows that the optimal procurement and delivery policy minimizes the expected total cost of the model. Using a test problem, the inventory requirements at each stage of production and their corresponding costs are calculated. From the analysis, it is shown that the rate and direction change of total cost is turned to positive when delivery rates per batch reaches close to the optimal value and the minimum cost is achieved at the optimal delivery rate. Also, it is shown that total incremental cost is monotonically increasing, if the finished product batch size is increased, and if, inventory cost rates are increased. We examine a set of numerical examples that reveal the insights into the procurement-delivery policy and the performance of such an assembly type inventory model.     

A worst-case analysis for the split delivery vehicle routing problem with minimum delivery amounts

In the vehicle routing problem (VRP), a fleet of vehicles must service the demands of customers in a least-cost way. In the split delivery vehicle routing problem (SDVRP), multiple vehicles can service the same customer by splitting the deliveries. By allowing split deliveries, savings in travel costs of up to 50 % are possible, and this bound is tight. Recently, a variant of the SDVRP, the split delivery vehicle routing problem with minimum delivery amounts (SDVRP-MDA), has been introduced. In the SDVRP-MDA, split deliveries are allowed only if at least a minimum fraction of a customer’s demand is delivered by each visiting vehicle. We perform a worst-case analysis on the SDVRP-MDA to determine tight bounds on the maximum possible savings.     

Complexity of flow shop scheduling problems with transportation constraints

In most manufacturing and distribution systems, semi-finished jobs are transferred from one processing facility to another by transporters such as Automated Guided Vehicles, robots and conveyors, and finished jobs are delivered to warehouses or customers by vehicles such as trucks.This paper investigates two-machine flow shop scheduling problems taking transportation into account. The finished jobs are transferred from the processing facility and delivered to customers by truck. Both transportation capacity and transportation times are explicitly taken into account in these models. We study the class of flow shop problems by analysing their complexity. For the makespan objective function, we prove that this problem is strongly NP-hard when the capacity of a truck is limited to two or three parts with an unlimited buffer at the output of the each machine. This problem with additional constraints, such as blocking, is also proven to be strongly NP-hard.     

An acceleration of Erlenkotter-Körkel’s algorithms for the uncapacitated facility location problem

This contribution is focused on an acceleration of branch and bound algorithms for the uncapacitated facility location problem. Our approach is based on the well-known Erlenkotters’ procedures and Körkels’ multi-ascent and multi-adjustment algorithms, which have proved to be the efficient tools for solving the large-sized instances of the uncapacitated facility location problem. These two original approaches were examined and a thorough analysis of their performance revealed how each particular procedure contributes to the computational time of the whole algorithms. These analyses helped us to focus our effort on the most frequent procedures. The unique contribution of this paper is a new dual ascent procedure. This procedure leads to considerable acceleration of the lower bound computation process and reduces the resulting computational time. To demonstrate more efficient performance of amended algorithms we present the results of extensive numerical experiments.     

A Column Generation Approach to Delivery Planning over Time with Inhomogeneous Service Providers and Service Interval Constraints

We consider a problem of delivery planning over multiple time periods. Deliveries must be made to customers having nominated demand in each time period. Demand must be met in each time period by use of some combination of inhomogeneous service providers. Each service provider has a different delivery capacity, different cost of delivery to each customer, a different utilisation requirement, and different rules governing the spread of deliveries in time. The problem is to plan deliveries so as to minimise overall costs, subject to demand being met and service rules obeyed. A natural integer programming model was found to be intractable, except on problems with loose demand constraints, with gaps between best lower bound and best feasible solution of up to 35.1%, with an average of 15.4% over the test data set. In all but the problem with loosest demand constraints, Cplex 6.5 applied to this formulation failed to find the optimal solution before running out of memory. However a column generation approach improved the lower bound by between 0.6% and 21.9%, with an average of 9.9%, and in all cases found the optimal solution at the root node, without requiring branching.     

Exact and heuristic methods for the selective maintenance problem

We present in this paper, new resolution methods for the selective maintenance problem. This problem consists in finding the best choice of maintenance actions to be performed on a multicomponent system, so as to maximize the system reliability, within a time window of a limited duration. When the number of components of the system is important, this combinatorial problem is not easy to solve, in particular because of the nonlinear objective function modeling the system reliability. This problem did not receive much attention yet. Consequently, rare are the effective resolution methods that are offered to the user. We thus developed heuristics and an exact method based on a branch and bound procedure, which we apply to various system configurations. We compare the obtained results, and we evaluate the best method to be used in various situations.     

Computing Approximate Solutions of the Maximum Covering Problem with GRASP

We consider the maximum covering problem, a combinatorial optimization problem that arises in many facility location problems. In this problem, a potential facility site covers a set of demand points. With each demand point, we associate a nonnegative weight. The task is to select a subset of p > 0 sites from the set of potential facility sites, such that the sum of weights of the covered demand points is maximized. We describe a greedy randomized adaptive search procedure (GRASP) for the maximum covering problem that finds good, though not necessarily optimum, placement configurations. We describe a well-known upper bound on the maximum coverage which can be computed by solving a linear program and show that on large instances, the GRASP can produce facility placements that are nearly optimal.     

A multi-visit flexible-docking vehicle routing problem with drones for simultaneous pickup and delivery services

This study investigates a multi-visit flexible-docking vehicle routing problem that uses a truck and drone fleet to fulfill pickup and delivery requests in rural areas. In this collaborative truck–drone system, each drone may serve multiple customers per trip (multi-visit services), dock to the same or different truck from where it launched (flexible docking), and perform simultaneous pickup and delivery. These characteristics complicate the temporal, spatial, and loading synchronization for trucks and drones, making the decisions of order allocation and vehicle routing highly interdependent and intractable. This problem is formulated as a mixed-integer linear programming model and solved by a tailored adaptive large neighborhood search metaheuristic. Numerical experiments are conducted on sparse rural networks to demonstrate the efficiency of the proposed method. We observe that the proposed truck–drone system shows an average cost saving of 34% compared to the truck-only case. Moreover, deep insights into the impacts of multi-visit services, flexible docking, and simultaneous pickup and delivery on the performance of the truck–drone system are discussed.