Simple Heuristics for the Vehicle Routeing Problem with Soft Time Windows

We describe three simple heuristics for the vehicle routeing problem with customer time windows that can be violated by paying appropriate penalties. The customer demands are known, and a homogeneous fleet of vehicles stationed at a single depot is considered. The penalty payable to a customer is assumed to be a linear function of the amount of time window violation. Upper limits are imposed on both the penalty payable and the waiting time allowed at any customer. At each customer in a route, the PC-based heuristics simultaneously determine the actual time to begin service, and the next customer to serve. To achieve this, each heuristic uses different measures to compare the cost of waiting and penalty payable, with the benefit obtained by leaving immediately for the next customer. Computational results on a set of benchmark problems show that the procedure is efficient and enables significant reduction in the number of vehicles required and/or the total route distances while controlling both customer penalties and waiting times.     

Admission control strategies for tandem Markovian loss systems

Motivated by communication networks, we study an admission control problem for a Markovian loss system comprised of two finite capacity service stations in tandem. Customers arrive to station 1 according to a Poisson process, and a gatekeeper, who has complete knowledge of the number of customers at both stations, decides whether to accept or reject each arriving customer. If a customer is rejected, a rejection cost is incurred. If an admitted customer finds that station 2 is full at the time of his service completion at station 1, he leaves the system and a loss cost is incurred. The goal is to find easy-to-implement policies that minimize long-run average cost per unit time. We formulate two intuitive, extremal policies and provide analytical results on their performances. We also present necessary and/or sufficient conditions under which each of these policies is optimal. Next, we show that for some states of the system it is always optimal to admit new arrivals. We also fully characterize the optimal policy when the capacity of each station is two and discuss some characteristics of optimal policies in general. Finally, we design heuristic admission control policies using these insights. Numerical experiments indicate that these heuristic policies yield near-optimal long-run average cost performance.     

Waiting time approximation in multi-class queueing systems with multiple types of class-dependent interruptions

We consider a single-server queue subject to class-dependent interruptions motivated by vessel queueing at entrances of waterways. Two classes of customers and k types of possibly simultaneous and class-dependent service interruptions are considered. We have employed service completion time analysis and proposed approximations to obtain the expected waiting time of a customer (vessel) in the queue.     

Integrated production and allocation policies with one direct shipping option

We consider a single period inventory problem in which a supplier faces stochastic demands and customer specific waiting costs from multiple customers. The objective is to develop integrated production, allocation, and distribution policies so that the total production and customer waiting costs are minimized. We present an optimal policy for the two customer problem and derive a heuristic for a general problem based on the structural results of the two customer case. We show, numerically, that the heuristic performs very well with error bounds of less than 2% on average, while typical approximations may lead to significant sub-optimality.     

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.     

The Economic Service Rate

This paper considers the problem of finding an optimal or economic service rate in queueing situations that can be modelled as birth-death processes. The costs and revenues considered are a cost for waiting, a cost for operating the server, and a revenue for each customer served. The paper derives certain optimality conditions that must be met in order that the service rate is optimal. These results are then applied to find economic service rates from graphs.     

A hybrid two-stage transportation and batch scheduling problem

We study the coordinated scheduling problem of hybrid batch production on a single batching machine and two-stage transportation connecting the production, where there is a crane available in the first-stage transportation that transports jobs from the warehouse to the machine and there is a vehicle available in the second-stage transportation to deliver jobs from the machine to the customer. As the job to be carried out is big and heavy in the steel industry, it is reasonable assumed that both the crane and the vehicle have unit capacity. The batching machine processes a batch of jobs simultaneously. Each batch occur a setup cost. The objective is to minimize the sum of the makespan and the total setup cost. We prove that this problem is strongly NP-hard. A polynomial time algorithm is proposed for a case where the job transportation times are identical on the crane or the vehicle. An efficient heuristic algorithm for the general problem is constructed and its tight worst-case bound is analyzed. In order to further verify the performance of the proposed heuristics, we develop a lower bound on the optimal objective function. Computational experiments show that the heuristic algorithm performs well on randomly generated problem instances.     

Stochastic scheduling of parallel queues with set-up costs

We consider the problem of allocating a single server to a system of queues with Poisson arrivals. Each queue represents a class of jobs and possesses a holding cost rate, general service distribution, and a set-up cost. The objective is to minimize the expected cost due to the waiting of jobs and the switching of the server. A set-up cost is required to effect an instantaneous switch from one queue to another. We partially characterize an optimal policy and provide a simple heuristic scheduling policy. The heuristic's performance is evaluated in the cases of two and three queues by comparison with a numerically obtained optimal policy. Simulation results are provided to demonstrate the effectiveness of our heuristic over a wide range of problem instances with four queues.     

Optimal control for parallel queues with a single batch server

We consider a queueing system with multiple Poisson arrival queues and a single batch server that has infinite capacity and a fixed service time. The problem is to allocate the server at each moment to minimize the long-run average waiting cost. We propose a Cost-Arrival Weighted (CAW) policy for this problem based on the structure of the optimal policy of a corresponding fluid model. We show that this simple policy enjoys a superior performance by numerical experiments.     

A GRASP heuristic for the manufacturing cell formation problem

In this work, we address the Manufacturing Cell Formation Problem (MCFP). Cellular Manufacturing is a production strategy that has emerged to reduce materials handling and set up times in order to reduce lead times in production systems and to improve customer??s service levels while reducing costs. We propose a GRASP heuristic to obtain lower bounds for the optimal solution of the problem. To evaluate the performance of the proposed method, we test the heuristic with different instances from the literature and compare the results obtained with those provided by other heuristic methods from the literature. According to the obtained results, the proposed GRASP procedure provides good quality lower bounds with reasonable computational effort.     

Managing a portfolio of long term service agreements

Long-term service agreements (LTSAs) for the maintenance of capital-intensive equipments such as gas turbines and aircraft engines are gaining wide acceptance. A typical LTSA contract spans over a period of around 10 years making a manufacturer fully responsible for maintaining the customer equipment. In this paper, we address the management of a portfolio of such contracts from the manufacturer’s perspective. The goal is to meet all the service requirements imposed by the contracts while minimizing total cost incurred. We develop a deterministic integer programming model to generate the optimal maintenance schedules that minimize the total portfolio cost. We then propose two heuristic algorithms for the problem.     

Batching deteriorating items with applications in computer communication and reverse logistics

We study two deterministic scheduling problems that combine batching and deterioration features. In both problems, there is a certain demand for identical good quality items to be produced in batches. In the first problem, each batch is assigned an individual machine that requires a cost and a time to be activated. All the machines are identical, work in parallel, and always produce good quality items. All the items are available at time zero and they deteriorate while waiting for production. Deterioration results in a linear increase of time and cost of production. In the second problem, there is a single machine that produces good quality as well as defective items in batches. Each batch is preceded by a setup time and requires a setup cost. Defective items have to be reworked on the same machine. They deteriorate while waiting for rework. At a time to be decided, the machine switches from production to rework defective items of the current batch. After rework, every defective item has the required good quality. In both problems, the objective is to find batch partitioning such that a linear combination of the production cost and production completion time is minimized. The two problems are observed at computer service providers and also reverse logistics. In computer service providers, machines and items correspond to communication service channels and information transfer tasks, respectively. We reduce both problems to minimizing a function of one variable representing the number of batches. In an optimal solution of either problem, there are at most two different batch sizes. Linear time algorithms are proposed for both problems.     

To wait or not to wait: Strategic behaviors in an observable batch-service queueing system

This paper deals with an observable batch service queueing system in which customers rationally choose whether to form a batch with another customer or not, in addition to deciding whether or not to join the queue. When choosing whether to form a batch, a customer in an incomplete batch decides on an optimal waiting time for the next customer to arrive and share the service fee. When choosing whether to join the queue, customers follow a threshold strategy, which depends on the strategy identified in the former game.     

Optimal inventory replenishment policy for a queueing system with finite waiting room capacity

We treat an inventory control problem in a facility that provides a single type of service for customers. Items used in service are supplied by an outside supplier. To incorporate lost sales due to service delay into the inventory control, we model a queueing system with finite waiting room and non-instantaneous replenishment process and examine the impact of finite buffer on replenishment policies. Employing a Markov decision process theory, we characterize the optimal replenishment policy as a monotonic threshold function of reorder point under the discounted cost criterion. We present a simple procedure that jointly finds optimal buffer size and order quantity.     

客源充足情境下的customer-intensive服务策略研究

在customer-intensive服务中服务速度越慢,顾客的效用就越高,然而等待时间也随之变长;而服务商则需对服务速度和价格进行决策,以求获得最优收益。本文基于客源丰富的服务垄断商对此问题采用M/M/1排队模型进行了研究,将顾客成本细分为时间成本和焦虑成本,给出了最优服务速度和价格。研究发现,单位焦虑成本的增加造成了服务商收益的减少,但对收益的影响要小于单位时间成本。最后,提出了服务商投入一定的服务成本来减少焦虑成本的策略,以达到获取更高收益的目的,并证明了策略的有效性。     

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.     

Multi-source facility location–allocation and inventory problem

We consider a joint facility location–allocation and inventory problem that incorporates multiple sources of warehouses. The problem is motivated by a real situation faced by a multinational applied chemistry company. In this problem, multiple products are produced in several plants. Warehouse can be replenished by several plants together because of capabilities and capacities of plants. Each customer in this problem has stochastic demand and certain amount of safety stock must be maintained in warehouses so as to achieve certain customer service level. The problem is to determine number and locations of warehouses, allocation of customers demand and inventory levels of warehouses. The objective is to minimize the expected total cost with the satisfaction of desired demand weighted average customer lead time and desired cycle service level. The problem is formulated as a mixed integer nonlinear programming model. Utilizing approximation and transformation techniques, we develop an iterative heuristic method for the problem. An experiment study shows that the proposed procedure performs well in comparison with a lower bound.     

A real-time decision rule for an inventory system with committed service time and emergency orders

In this paper, we study the inventory system of an online retailer with compound Poisson demand. The retailer normally replenishes its inventory according to a continuous review (nQ, R) policy with a constant lead time. Usually demands that cannot be satisfied immediately are backordered. We also assume that the customers will accept a reasonable waiting time after they have placed their orders because of the purchasing convenience of the online system. This means that a sufficiently short waiting time incurs no shortage costs. We call this allowed waiting time “committed service time”. After this committed service time, if the retailer is still in shortage, the customer demand must either be satisfied with an emergency supply that takes no time (which is financially equivalent to a lost sale) or continue to be backordered with a time-dependent backorder cost. The committed service time gives an online retailer a buffer period to handle excess demands. Based on real-time information concerning the outstanding orders of an online retailer and the waiting times of its customers, we provide a decision rule for emergency orders that minimizes the expected costs under the assumption that no further emergency orders will occur. This decision rule is then used repeatedly as a heuristic. Numerical examples are presented to illustrate the model, together with a discussion of the conditions under which the real-time decision rule provides considerable cost savings compared to traditional systems.     

A Lagrangian relaxation-based heuristic for the vehicle routing with full container load

We address a problem of vehicle routing that arises in picking up and delivering full container load from/to an intermodal terminal. The substantial cost and time savings are expected by efficient linkage between pickup and delivery tasks, if the time of tasks and the suitability of containers for cargo allow. As this problem is NP-hard, we develop a subgradient heuristic based on a Lagrangian relaxation which enables us to identify a near optimal solution. The heuristic consists of two sub-problems: the classical assignment problem and the generalized assignment problem. As generalized assignment problem is also NP-hard, we employ an efficient solution procedure for a bin packing based problem, which replaces the generalized assignment problem. The heuristic procedure is tested on a wide variety of problem examples. The test results demonstrate that the procedure developed here can efficiently solve large instances of the problem.