Market selection decisions for inventory models with price-sensitive demand

In the majority of classical inventory theory literature, demand arises from exogenous sources upon which the firm has little or no control. In many practical contexts, however, aggregate demand is comprised of individual demands from a number of distinct customers or markets. This introduces new dimensions to supply chain planning problems involving the selection of markets or customers to include in the demand portfolio. We present a nonlinear, combinatorial optimization model to address planning decisions in both deterministic and stochastic settings, where a firm constructs a demand portfolio from a set of potential markets having price-sensitive demands. We first consider a pricing strategy that dictates a single price throughout all markets and provide an efficient algorithm for maximizing total profit. We also analyze the model under a market-specific pricing policy and describe its optimal solution. An extensive computational study characterizes the effects of key system parameters on the optimal value of expected profit, and provides some interesting insights on how a given market’s characteristics can affect optimal pricing decisions in other markets.     

Designing delivery districts for the vehicle routing problem with stochastic demands

This paper considers the problem of designing districts for vehicle routing problems with stochastic demands. In particular, demands are assumed to be uncertain at the time when the districts are made, and these are revealed only after the districting decisions are determined. Tabu search and multistart heuristics for this stochastic districting problem are developed and compared. Computational results show that tabu search is superior over multistart.     

An approximation algorithm for the pickup and delivery vehicle routing problem on trees

This paper presents an approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot where there are two types of demands, pickup demand and delivery demand. Customers are located on nodes of the tree, and each customer has a positive demand of pickup and/or delivery.Demands of customers are served by a fleet of identical vehicles with unit capacity. Each vehicle can serve pickup and delivery demands. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. In each tour, a vehicle begins at the depot with certain amount of goods for delivery, visits a subset of the customers in order to deliver and pick up goods and returns to the depot. At any time during the tour, a vehicle must always satisfy the capacity constraint, i.e., at any time the sum of goods to be delivered and that of goods that have been picked up is not allowed to exceed the vehicle capacity. We propose a 2-approximation algorithm for the problem.     

Dynamic pricing of multiple home delivery options

Online grocers accept delivery bookings and have to deliver groceries to consumers’ residences. Grocery stores operate on very thin margins. Therefore, a critical question that an online grocery store needs to address is the cost of home delivery operations. In this paper, we develop a Markov decision process-based pricing model that recognizes the need to balance utilization of delivery capacity by the grocer and the need to have the goods delivered at the most convenient time for the customer. The model dynamically adjusts delivery prices as customers arrive and make choices. The optimal prices have the following properties. First, the optimal prices are such that the online grocer gains the same expected payoff in the remaining booking horizon, regardless of the delivery option independently chosen by a consumer. Second, with unit order sizes, delivery prices can increase due to dynamic substitution effects as there is less time left in the booking horizon.     

Routing relatively few customers per route

This paper presents a modification of the well-known Solomon (1987) sequential insertion heuristic I1 for the Vehicle Routing Problem with Time Windows (VRPTW). VRPTW involves servicing customers within a pre-specified service time window by homogeneously capacitated vehicles from a single depot. By using two new measures for the additional time needed to insert a customer in the route, significantly better solutions are obtained for relatively short routes compared to the original Solomon (1987) sequential insertion heuristic I1. Because high-quality initial heuristics often allow local searches and metaheuristics to achieve better solutions more quickly, the new approach is likely to help generating better solutions to practical routing problems.     

Integer linear programming models for a cement delivery problem

We consider a cement delivery problem with an heterogeneous fleet of vehicles and several depots. The demands of the customers are typically larger than the capacity of the vehicles which means that most customers are visited several times. This is a split delivery vehicle routing problem with additional constraints. We first propose a two phase solution method that assigns deliveries to the vehicles, and then builds vehicle routes. Both subproblems are formulated as integer linear programming problems. We then show how to combine the two phases in a single integer linear program. Experiments on real life instances are performed to compare the performance of the two solution methods.     

Bundle pricing of inventories with stochastic demand

We consider a retailer selling a fixed inventory of two perishable products over a finite horizon. Assuming Poisson arrivals and a bivariate reservation price distribution, we determine the optimal product and bundle prices that maximize the expected revenue. Our results indicate that the performances of mixed bundling, pure bundling and unbundled sales strategies heavily depend on the parameters of the demand process and the initial inventory levels. Bundling appears to be most effective with negatively correlated reservation prices and high starting inventory levels. When the starting inventory levels are equal and in excess of average demand, most of the benefits of bundling can be achieved through pure bundling. However, the mixed bundling strategy dominates the other two when the starting inventory levels are not equal. We also observe that an incorrect modeling of the reservation prices may lead to significant losses. The model is extended to allow for price changes during the selling horizon. It is shown that offering price bundles mid-season may be more effective than changing individual product prices.     

An approximation algorithm for vehicle routing with compatibility constraints

We study a multiple-vehicle routing problem with a minimum makespan objective and compatibility constraints. We provide an approximation algorithm and a nearly-matching hardness of approximation result. We also provide computational results on benchmark instances with diverse sizes showing that the proposed algorithm (i) has a good empirical approximation factor, (ii) runs in a short amount of time and (iii) produces solutions comparable to the best feasible solutions found by a direct integer program formulation.     

Optimal static pricing for a service facility with holding costs

We study a service facility modelled as a single-server queueing system with Poisson arrivals and limited or unlimited buffer size. In systems with unlimited buffer size, the service times have general distributions, whereas in finite buffered systems service times are exponentially distributed. Arriving customers enter if there is room in the facility and if they are willing to pay the posted price. The same price is charged to all customers at all times (static pricing). The service provider is charged a holding cost proportional to the time that the customers spend in the system. We demonstrate that there is a unique optimal price that maximizes the long-run average profit per unit time. We also investigate how optimal prices vary as system parameters change. Finally, we consider buffer size as an additional decision variable and show that there is an optimal buffer size level that maximizes profit.     

The complexity of branch-and-price algorithms for the capacitated vehicle routing problem with stochastic demands

The capacitated vehicle routing problem with stochastic demands (CVRPSD) is a variant of the deterministic capacitated vehicle routing problem where customer demands are random variables. While the most successful formulations for several deterministic vehicle-routing problem variants are based on a set-partitioning formulation, adapting such formulations for the CVRPSD under mild assumptions on the demands remains challenging. In this work we provide an explanation to such challenge, by proving that when demands are given as a finite set of scenarios, solving the LP relaxation of such formulation is strongly NP-Hard. We also prove a hardness result for the case of independent normal demands.     

Static pickup and delivery problems: a classification scheme and survey

Pickup and delivery problems constitute an important class of vehicle routing problems in which objects or people have to be collected and distributed. This paper introduces a general framework to model a large collection of pickup and delivery problems, as well as a three-field classification scheme for these problems. It surveys the methods used for solving them. This invited paper is discussed in the comments available at: , , , , .     

A heuristic algorithm for the free newspaper delivery problem

This paper addresses the problem of finding an effective distribution plan to deliver free newspapers from a production plant to subway, bus, or tram stations. The overall goal is to combine two factors: first, the free newspaper producing company wants to minimize the number of vehicle trips needed to distribute all newspapers produced at the production plant. Second, the company is interested in minimizing the time needed to consume all newspapers, i.e., the time needed to get all the newspapers taken by the final readers. The resulting routing problem combines aspects of the vehicle routing problem with time windows, the inventory routing problem, and additional constraints related to the production schedule. We propose a formulation and different heuristic approaches, as well as a hybrid method. Computational tests with real world data show that the hybrid method is the best in various problem settings.     

Optimal worst-case pricing for a logit demand model with network effects

We consider optimal pricing problems for a product that experiences network effects. Given a price, the sales quantity of the product arises as an equilibrium, which may not be unique. In contrast to previous studies that take a best-case view when there are multiple equilibrium sales quantities, we maximize the seller’s revenue assuming that the worst-case equilibrium quantity will arise in response to a chosen price. We compare the best- and worst-case solutions, and provide asymptotic analysis of revenues.     

New mathematical models of the generalized vehicle routing problem and extensions

The generalized vehicle routing problem (GVRP) is an extension of the vehicle routing problem (VRP) and was introduced by Ghiani and Improta [1]. The GVRP is the problem of designing optimal delivery or collection routes from a given depot to a number of predefined, mutually exclusive and exhaustive node-sets (clusters) which includes exactly one node from each cluster, subject to capacity restrictions. The aim of this paper is to provide two new models of the GVRP based on integer programming. The first model, called the node formulation is similar to the Kara-Bekta? formulation [2], but produces a stronger lower bound. The second one, called the flow formulation, is completely new. We show as well that under specific circumstances the proposed models of the GVRP reduces to the well known routing problems. Finally, the GVRP is extended for the case in which the vertices of any cluster of each tour are contiguous. This case is defined as the clustered generalized vehicle routing problem and both of the proposed formulations of GVRP are adapted to clustered case.     

CLOVES: A cluster-and-search heuristic to solve the vehicle routing problem with delivery and pick-up

This paper addresses the vehicle routing problem with sequence-constrained delivery and pick-up (VRPDP). We propose a multi-phase constructive heuristic that clusters nodes based on proximity, orients them along a route using shrink-wrap algorithm and allots vehicles using generalized assignment procedure. We employ genetic algorithm for an intensive final search. Trials on a large number of test-problems have yielded encouraging results.     

A hybrid differential evolution algorithm to vehicle routing problem with fuzzy demands

In this paper, the vehicle routing problem with fuzzy demands (VRPFD) is considered, and a fuzzy chance constrained program model is designed, based on fuzzy credibility theory. Then stochastic simulation and differential evolution algorithm are integrated to design a hybrid intelligent algorithm to solve the fuzzy chance constrained program model. Moreover, the influence of the dispatcher preference index on the final objective of the problem is discussed using stochastic simulation, and the best value of the dispatcher preference index is obtained.     

Capacitated procurement planning with price-sensitive demand and general concave-revenue functions

This paper develops effective solution methods for discrete-time, finite-horizon procurement planning problems with economies of scale in procurement, price-sensitive demand, and time-invariant procurement capacities. Our models consider general concave-revenue functions in each time period, and seek to maximize total revenue less procurement and inventory holding costs. We consider the case in which prices may vary dynamically, as well the important practical case in which a constant price is required during the planning horizon. Under mild conditions on the revenue function properties, we provide polynomial-time solution methods for this problem class. The structural properties of optimal solutions that lead to efficient solution methods also serve to sharpen intuition regarding optimal demand management strategies in complex planning situations.     

Dynamic pickup and delivery problems

In the last decade, there has been an increasing body of research in dynamic vehicle routing problems. This article surveys the subclass of those problems called dynamic pickup and delivery problems, in which objects or people have to be collected and delivered in real-time. It discusses some general issues as well as solution strategies.     

Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints

Electric bus scheduling problem can be defined as vehicle scheduling problem with route and fueling time constraints (VSPRFTC). Every vehicle’s travel miles (route time) after charging is limited, thus the vehicle must be recharged after taking several trips and the minimal charging time (fueling time) must be satisfied. A multiple ant colony algorithm (ACA) was presented to solve VSPRFTC based on ACA used to solve traveling salesman problem (TSP), a new metaheuristic approach inspired by the foraging behavior of real colonies of ants. The VSPRFTC considered in this paper minimizes a multiple, hierarchical objective function: the first objective is to minimize the number of tours (or vehicles) and the second is to minimize the total deadhead time. New improvement of ACA as well as detailed operating steps was provided on the basis of former algorithm. Then in order to settle contradiction between accelerating convergence and avoiding prematurity or stagnation, improvement on route construction rule and Pheromone updating rule was adopted. A group feasible trip sets (blocks) had been produced after the process of applying ACA. In dealing with the fueling time constraint a bipartite graphic model and its optimization algorithm are developed for trip set connecting in a hub and spoke network system to minimize the number of vehicle required. The maximum matching of the bipartite graph is obtained by calculating the maximum inflow with the Ford–Fulkerson algorithm. At last, an example was analyzed to demonstrate the correctness of the application of this algorithm. It proved to be more efficient and robust in solving this problem.