Dynamic scheduling of recreational rental vehicles with revenue management extensions

The rental fleet scheduling problem (RFSP) arises in vehicle-rental operations that offer a wide variety of vehicle types to customers, and allow a rented vehicle to ‘migrate’ to a setdown depot other than the pickup depot.When there is a shortage of vehicles of a particular type at a depot, vehicles may be relocated to that depot, or vehicles of similar types may be substituted.The RFSP involves assigning vehicles to rentals so as to minimise the costs of these operations, and arises in both static and online contexts. The authors have adapted a well-known assignment algorithm for application in the online context. In addition, a network-flow algorithm with more comprehensive coverage of problem conditions is used to investigate the determination of rental pricing using revenue management principles. The paper concludes with an outline of the algorithms’ use in supporting the operations of a large recreational vehicle rental company.     

A single-resource revenue management problem with random resource consumptions

We study a single-resource multi-class revenue management problem where the resource consumption for each class is random and only revealed at departure. The model is motivated by cargo revenue management problems in the airline and other shipping industries. We study how random resource consumption distribution affects the optimal expected profit and identify a preference acceptance order on classes. For a special case where the resource consumption for each class follows the same distribution, we fully characterize the optimal control policy. We then propose two easily computable heuristics: (i) a class-independent heuristic through parameter scaling, and (ii) a decomposition heuristic that decomposes the dynamic programming formulation into a collection of one-dimensional problems. We conduct extensive numerical experiments to investigate the performance of the two heuristics and compared them with several widely studied heuristic policies. Our results show that both heuristics work very well, with class-independent heuristic slightly better between the two. In particular, they consistently outperform heuristics that ignore demand and/or resource consumption uncertainty. Our results demonstrate the importance of considering random resource consumption as another problem dimension in revenue management applications.     

A heuristic approach for the truck and trailer routing problem

In this paper, we propose an approach based on mathematical programming and local search to cope with the truck and trailer vehicle routing problem. The mathematical programming framework models two subproblems that are solved sequentially, that is, the customer-route assignment problem (CAP), with the objective of minimizing the fleet size used to service clients, and the route definition problem, with the objective of minimizing the total tour length given the set of clients assigned to each vehicle. Since the route assignment model can return infeasible solutions, the local search plays the role of possibly retrieving a feasible solution. The mathematical formulations and the local search work iteratively, embedded in a multiple restarting mechanism able to diversify solutions by (i) identifying additional constraints for the CAP formulation to be taken into account during the algorithm progress, (ii) using a tabu like customer-route matrix to avoid assignments already analysed in the previous iterations of the algorithm. Also a lower bound to assess the solution quality is given. Experiments and comparison with competing approaches suggest that the results of the proposed machinery are promising, producing, on average,a smaller total tour lengths on benchmarks.     

On the structural properties of a discrete-time single product revenue management problem

We consider a multi-period revenue management problem in which multiple classes of demand arrive over time for the common inventory. The demand classes are differentiated by their revenues and their arrival distributions. We investigate monotonicity properties of varying problem parameters on the optimal reward and the policy.     

Using revenue sharing to create win–win in the video rental supply chain

Recent developments in video rental supply chains seem to indicate that revenue sharing contracts are beneficial to all parties involved in the industry. This paper illustrates a theoretical underpinning of the observed practice. A video rental supply chain is modelled to study pricing and replenishment decision making by the two autonomous firms in the chain, namely a movie studio producing the tapes and a video rental shop renting the tapes to customers. In the model the movie studio is to set the price for selling the tapes to the video rental store and the video rental shop must decide the number of copies of the new movie videotape it should purchase. The paper illustrates that revenue sharing contract can optimize the chain and bring win–win situations to the players in the industry.     

A stochastic approximation method for the single-leg revenue management problem with discrete demand distributions

We consider the problem of optimally allocating the seats on a single flight leg to the demands from multiple fare classes that arrive sequentially. It is well-known that the optimal policy for this problem is characterized by a set of protection levels. In this paper, we develop a new stochastic approximation method to compute the optimal protection levels under the assumption that the demand distributions are not known and we only have access to the samples from the demand distributions. The novel aspect of our method is that it works with the nonsmooth version of the problem where the capacity can only be allocated in integer quantities. We show that the sequence of protection levels generated by our method converges to a set of optimal protection levels with probability one. We discuss applications to the case where the demand information is censored by the seat availability. Computational experiments indicate that our method is especially advantageous when the total expected demand exceeds the capacity by a significant margin and we do not have good a priori estimates of the optimal protection levels.     

A stochastic approach to professional services firms’ revenue optimization

Regarding professional service time as perishable goods, it should be possible to directly migrate the successful airline revenue management techniques to professional services firms (PSFs) for their analogous business characters. However, there are salient differences between airlines and PSFs should be highlighted—the network structure of length-of-continuance and capacity allocation of multifunctional staff. Customers booking to be served from a first continuance time to a last continuance time in consecutive time continuance. Multifunctional professionals should be properly allocated to maximize the benefit. The arrival demands and lengths of service are stochastic in nature.     

A polyhedral approach to a production planning problem

Production planning in manufacturing industries is concerned with the determination of the production quantities (lot sizes) of some items over a time horizon, in order to satisfy the demand with minimum cost, subject to some production constraints. In general, production planning problems become harder when different types of constraints are present, such as capacity constraints, minimum lot sizes, changeover times, among others. Models incorporating some of these constraints yield, in general, NP-hard problems. We consider a single-machine, multi-item lot-sizing problem, with those difficult characteristics. There is a natural mixed integer programming formulation for this problem. However, the bounds given by linear relaxation are in general weak, so solving this problem by LP based branch and bound is inefficient. In order to improve the LP bounds, we strengthen the formulation by adding cutting planes. Several families of valid inequalities for the set of feasible solutions are derived, and the corresponding separation problems are addressed. The result is a branch and cut algorithm, which is able to solve some real life instances with 5 items and up to 36 periods. This revised version was published online in June 2006 with corrections to the Cover Date.     

A fuzzy-linguistic approach to a multi-criteria sequencing problem

In this paper, a fuzzy approach to a single machine scheduling problem is considered. In this approach, the system's variables are defined using linguistic terms. Each of these variables may take values described via fuzzy triangular numbers. The scheduling criteria are the common due date, the total earliness and tardiness and the controllable duration of the jobs' processing times. The aim is to determine the length of the processing times, to sequence the jobs in the machine and, finally, to determine the common due date in a near optimal way. The problem is solved using an algorithmic procedure, which is illustrated by means of an example.     

Revenue management approach to stochastic capacity allocation problem

To formulate stochastic capacity allocation problems in a manufacturing system, the concept and techniques of revenue management is applied in this research. It is assumed the production capacity is stochastic and hence its exact size cannot be forecasted in advance, at the time of planning. There are two classes of “frequent” and “occasional” customers demanding this capacity. The price rate as well as the penalty for order cancellation caused by overbooking is different for each class. The model is developed mathematically and we propose an analytical solution method. The properties of the optimal solution as well as the behavior of objective function are also analyzed. The objective function is not concave, in general. However, we prove it is a unimodal function and by taking advantage of this property, the optimal solution is determined.     

A relax-and-fix-based algorithm for the vehicle-reservation assignment problem in a car rental company

Empty repositions are a major problem for car rental companies that deal with special types of vehicles whose number of units is small. In order to meet reservation requirements concerning time and location, companies are forced to transfer cars between rental stations, bearing significant costs and increasing the environmental impact of their activity due to the fuel consumption and CO₂${\text{CO}}_2$ emission. In this paper, this problem is tackled under a vehicle-reservation assignment framework as a network-flow model in which the profit is maximized. The reservations are allocated considering the initial and future availability of each car, interdependencies between rental groups, and different reservation priorities. To solve this model, a relax-and-fix heuristic procedure is proposed, including a constraint based on local branching that enables and controls modifications between iterations. Using real instances, the value of this approach is established and an improvement of 33% was achieved when compared to the company’s current practices.     

A decomposition approach for a very large scale optimal diversity management problem

This paper focuses on the solution of the optimal diversity management problem formulated as a p-Median problem. The problem is solved for very large scale real instances arising in the car industry and defined on a graph with several tens of thousands of nodes and with several millions of arcs. The particularity is that the graph can consist of several non connected components. This property is used to decompose the problem into a series of p-Median subproblems of a smaller dimension. We use a greedy heuristic and a Lagrangian heuristic for each subproblem. The solution of the whole problem is obtained by solving a suitable assignment problem using a Branch-and-Bound algorithm.Received: June 2004 / Revised version: December 2004MSC classification: 49M29, 90C06, 90C27, 90C60All correspondence to: Antonio SforzaIgor Vasilev: Support for this author was provided by NATO grant CBP.NR.RIG.911258.     

A complementarity approach to a quasistatic multi-rigid-body contact problem

In this paper, we study the problem of predicting the quasistatic planar motion of a passive rigid body in frictional contact with a set of active rigid bodies. The active bodies can be thought of as the links of a mechanism or robot manipulator whose positions can be actively controlled by actuators. The passive body can be viewed as a grasped object, which moves only in response to contact forces and other external forces such as those due to gravity. We formulate this problem as a certain uncoupled complementarity problem, and show that it belongs to the class of NP-complete problems. Finally, numerical results of our proposed linear programming-based solution algorithm for this class of problems are presented and compared to the only other currently available solution algorithm.The research of this author was based on work supported by the National Science Foundation under grants DDM-9104078 and CCR-9213739.The research of this author was partially supported by the National Science Foundation under grant IRI-9304734, the Texas Advanced Technology Program under grant 999903-095, and the Texas Advanced Research Program under grant 999903-078.     

A heuristic approach to a weighted maxmin dispersion problem

In this paper, the nonconvex form of the weighted maxmin dispersionproblem is converted to a form involving the maximization ofconvex functions over a polytope, for which algorithms exist.A heuristic approach is given, together with associated resultson optimality and bounds on loss of optimality.     

A proximal iterative approach to a non-convex optimization problem

We consider a variable Krasnosel’skii-Mann algorithm for approximating critical points of a prox-regular function or equivalently for finding fixed-points of its proximal mapping prox_λf. The novelty of our approach is that the latter is not non-expansive any longer. We prove that the sequence generated by such algorithm (via the formula x_k+1=(1−α_k)x_k+α_kprox_λkfx_k, where (α_k) is a sequence in (0,1)), is an approximate fixed-point of the proximal mapping and converges provided that the function under consideration satisfies a local metric regularity condition.     

A generating functionology approach to a problem of Wilf

Wilf posed the following problem: determine asymptotically as n→∞ the probability that a randomly chosen part size in a randomly chosen composition of n has multiplicity m. One solution of this problem has been given by two of the authors 〈http://www.csc.ncsu.edu/faculty/savage/〉. In this paper, we study this question using the techniques of generating functions and singularity analysis.     

A Lagrangian relaxation approach for network inventory control of stochastic revenue management with perishable commodities

Airline seat inventory control is the allocation of seats in the same cabin to different fare classes such that the total revenue is maximized. Seat allocation can be modelled as dynamic stochastic programs, which are computationally intractable in network settings. Deterministic and probabilistic mathematical programming models are therefore used to approximate dynamic stochastic programs. The probabilistic model, which is the focus of this paper, has a nonlinear objective function, which makes the solution of large-scale practical instances with off-the-shelf solvers prohibitively time consuming. In this paper, we propose a Lagrangian relaxation (LR) method for solving the probabilistic model by exploring the fact that LR problems are decomposable. We show that the solutions of the LR problems admit a simple analytical expression which can be resolved directly. Both the booking limit policy and the bid-price policy can be implemented using this method. Numerical simulations demonstrate the effectiveness of the proposed method.     

A constructive approach to Noether's problem

A general method is developed to attack Noether's Problem constructively by trying to find minimal bases consisting of rational invariants which are quotients of polynomials of small degrees. This approach turns out to be successful for many small groups and for most of the classical groups with their natural representations. The applications include affirmative answers to Noether's Problem for the conformal symplectic groups CSp _2n (q), for the simple subgroups Ω _n (q) of the orthogonal groups forn andq odd, for some other subgroups of orthogonal groups and for the special unitary groups SU _n (q ²). The author was supported by the Graduate College “Modelling and Scientific Computing in Mathematics and Science” during this work