Assortment Optimization under the Multinomial Logit Model with Random Choice Parameters

We consider assortment optimization problems under the multinomial logit model, where the parameters of the choice model are random. The randomness in the choice model parameters is motivated by the fact that there are multiple customer segments, each with different preferences for the products, and the segment of each customer is unknown to the firm when the customer makes a purchase. This choice model is also called the mixture‐of‐logits model. The goal of the firm is to choose an assortment of products to offer that maximizes the expected revenue per customer, across all customer segments. We establish that the problem is NP complete even when there are just two customer segments. Motivated by this complexity result, we focus on assortments consisting of products with the highest revenues, which we refer to as revenue‐ordered assortments. We identify specially structured cases of the problem where revenue‐ordered assortments are optimal. When the randomness in the choice model parameters does not follow a special structure, we derive tight approximation guarantees for revenue‐ordered assortments. We extend our model to the multi‐period capacity allocation problem, and prove that, when restricted to the revenue‐ordered assortments, the mixture‐of‐logits model possesses the nesting‐by‐fare‐order property. This result implies that revenue‐ordered assortments can be incorporated into existing revenue management systems through nested protection levels. Numerical experiments show that revenue‐ordered assortments perform remarkably well, generally yielding profits that are within a fraction of a percent of the optimal.     

Assortment optimisation problem: A distribution-free approach

Assortment optimisation is a critical decision that is regularly made by retailers. The decision involves a trade-off between offering a larger assortment of products but smaller inventories of each product and offering a smaller number of varieties with more inventory of each product. We propose a robust, distribution-free formulation of the assortment optimisation problem such that the assortment and inventory levels can be jointly optimised without making specific assumptions on the demand distributions of each product. We take a max-min approach to the problem that provides a guaranteed lower bound to the expected profit when only the mean and variance of the demand distribution are known. We propose and test three heuristic algorithms that provide solutions in O(nlog (n)) time and identify two cases where one of the heuristics is guaranteed to return optimal policies. Through numerical studies, we demonstrate that one of the heuristics performs extremely well, with an average optimality gap of 0.07% when simulated under varying conditions. We perform a sensitivity analysis of product and store demand attributes on the performance of the heuristic. Finally, we extend the problem by including maximum cardinality constraints on the assortment size and perform numerical studies to test the performance of the heuristics.     

A New Dynamic Programming Decomposition Method for the Network Revenue Management Problem with Customer Choice Behavior

In this paper, we propose a new dynamic programming decomposition method for the network revenue management problem with customer choice behavior. The fundamental idea behind our dynamic programming decomposition method is to allocate the revenue associated with an itinerary among the different flight legs and to solve a single‐leg revenue management problem for each flight leg in the airline network. The novel aspect of our approach is that it chooses the revenue allocations by solving an auxiliary optimization problem that takes the probabilistic nature of the customer choices into consideration. We compare our approach with two standard benchmark methods. The first benchmark method uses a deterministic linear programming formulation. The second benchmark method is a dynamic programming decomposition idea that is similar to our approach, but it chooses the revenue allocations in an ad hoc manner. We establish that our approach provides an upper bound on the optimal total expected revenue, and this upper bound is tighter than the ones obtained by the two benchmark methods. Computational experiments indicate that our approach provides significant improvements over the performances of the benchmark methods.     

Randomization Approaches for Network Revenue Management with Customer Choice Behavior

In this study, we present new approximation methods for the network revenue management problem with customer choice behavior. Our methods are sampling‐based and so can handle fairly general customer choice models. The starting point for our methods is a dynamic program that allows randomization. An attractive feature of this dynamic program is that the size of its action space is linear in the number of itineraries, as opposed to exponential. It turns out that this dynamic program has a structure that is similar to the dynamic program for the network revenue management problem under the so called independent demand setting. Our approximation methods exploit this similarity and build on ideas developed for the independent demand setting. We present two approximation methods. The first one is based on relaxing the flight leg capacity constraints using Lagrange multipliers, whereas the second method involves solving a perfect hindsight relaxation problem. We show that both methods yield upper bounds on the optimal expected total revenue. Computational experiments demonstrate the tractability of our methods and indicate that they can generate tighter upper bounds and higher expected revenues when compared with the standard deterministic linear program that appears in the literature.     

消费者导向类型与电商全渠道决策研究

从现实出发，基于不同消费者导向类型研究了电商的全渠道决策问题。首先建立电商单渠道销售的基础模型，并得出最优产品组合、价格和交付时间。在此基础上，给出了消费者为产品导向型和渠道导向型情况下电商采取全渠道决策的条件，得出双渠道产品组合、价格及交付时间的最优决策；并进行了数值验证。研究发现，同一渠道提供的产品其最优价格相同，最优交付时间只和消费者耐心程度及交付成本函数有关。若消费者为产品导向型，仅当双渠道运营成本之差较小且消费者耐心程度较低时，电商进入线下渠道才有利可图，且在线下渠道提供最受欢迎的产品，线上渠道提供剩余产品。若消费者为渠道导向型，电商进入线下渠道必然有利可图，且在线下渠道提供最受欢迎的产品，线上渠道提供所有产品。     

Myopic Analysis for Multi‐Echelon Inventory Systems with Batch Ordering and Nonstationary/Time‐Correlated Demands

We provide an exact myopic analysis for an N‐stage serial inventory system with batch ordering, linear ordering costs, and nonstationary demands under a finite planning horizon. We characterize the optimality conditions of the myopic nested batching newsvendor (NBN) policy and the myopic independent batching newsvendor (IBN) policy, which is a single‐stage approximation. We show that echelon reorder levels under the NBN policy are upper bounds of the counterparts under both the optimal policy and the IBN policy. In particular, we find that the IBN policy has bounded deviations from the optimal policy. We further extend our results to systems with martingale model of forecast evolution (MMFE) and advance demand information. Moreover, we provide a recursive computing procedure and optimality conditions for both heuristics which dramatically reduces computational complexity. We also find that the NBN problem under the MMFE faced by one stage has one more dimension for the forecast demand than the one faced by its downstream stage and that the NBN policy is optimal for systems with advance demand information and stationary problem data. Numerical studies demonstrate that the IBN policy outperforms on average the NBN policy over all tested instances when their optimality conditions are violated.     

When to Carry Eccentric Products? Optimal Retail Assortment under Consumer Returns

To understand whether retailers should consider consumer returns when merchandising, we study how the optimal assortment of a retailer is influenced by its return policy. The retailer selects its assortment from an exogenous set of horizontally differentiated products. Consumers make purchase and keep/return decisions in nested multinomial logit fashion. Our main finding is that the optimal assortment has a distinct structure for relatively strict return policies: it is optimal to offer a mix of the most popular and most eccentric products when the refund amount is sufficiently low, which can be viewed as a form of risk sharing between the retailer and consumers. In contrast, if the refund is sufficiently high or when returns are disallowed, the optimal assortment is composed of only the most popular products (a common finding in the literature). We provide preliminary empirical evidence for one of the key drivers of our results: more eccentric products have higher probability of return—conditional on purchase. In light of our analytical findings and managerial insights, we conclude that retailers should take returns into account when merchandising.     

Quality‐Speed Competition in Customer‐Intensive Services with Boundedly Rational Customers

We consider a system in which two competing servers provide customer‐intensive services and the service reward is affected by the length of service time. The customers are boundedly rational and choose their service providers according to a logit model. We demonstrate that the service provider revenue function is unimodal in the service rate, its decision variable, and show that the service rate competition has a unique and stable equilibrium. We then study the price decision under three scenarios with the price determined by a revenue‐maximizing firm, a welfare‐maximizing social planner, or two servers in competition. We find that the socially optimal price, subject to the requirement that the customer actual utility must be non‐negative, is always lower than the competition equilibrium price which, in turn, is lower than the revenue‐maximizing monopoly price. However, if the customer actual utility is allowed to be negative in social optimization, the socially optimal price can be higher than the other two prices in a large market.     

The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach

In this paper, we consider a variant of the Location-Routing Problem (LRP), namely the LRP with simultaneous pickup and delivery (LRPSPD). The LRPSPD seeks to minimize total cost by simultaneously locating the depots and designing the vehicle routes that satisfy pickup and delivery demand of each customer at the same time. We propose two polynomial-size mixed integer linear programming formulations for the problem and a family of valid inequalities to strengthen the formulations. While the first formulation is a node-based formulation, the second one is a flow-based formulation. Furthermore, we propose a two-phase heuristic approach based on simulated annealing, tp_SA, to solve the large-size LRPSPD and two initialization heuristics to generate an initial solution for the tp_SA. We then empirically evaluate the strengths of the proposed formulations with respect to their ability to find optimal solutions or strong lower bounds, and investigate the performance of the proposed heuristic approach. Computational results show that the flow-based formulation performs better than the node-based formulation in terms of the solution quality and the computation time on small-size problems. However, the node-based formulation can yield competitive lower bounds in a reasonable amount of time on medium-size problems. Meantime, the proposed heuristic approach is computationally efficient in finding good quality solutions for the LRPSPD.     

Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem

In a previous work we proposed a variable fixing heuristics for the 0-1 Multidimensional knapsack problem (01MDK). This approach uses fractional optima calculated in hyperplanes which contain the binary optimum. This algorithm obtained best lower bounds on the OR-Library benchmarks. Although it is very attractive in terms of results, this method does not prove the optimality of the solutions found and may fix variables to a non-optimal value. In this paper, we propose an implicit enumeration based on a reduced costs analysis which tends to fix non-basic variables to their exact values. The combination of two specific constraint propagations based on reduced costs and an efficient enumeration framework enable us to fix variables on the one hand and to prune significantly the search tree on the other hand. Experimentally, our work provides two main contributions: (1) we obtain several new optimal solutions on hard instances of the OR-Library and (2) we reduce the bounds of the number of items at the optimum on several harder instances.     

Integrated Order Scheduling and Packing

We consider an integrated production–distribution scheduling model in a make‐to‐order supply chain consisting of one supplier and one customer. The supplier receives a set of orders from the customer at the beginning of a planning horizon. The supplier needs to process all the orders at a single production line, pack the completed orders to form delivery batches, and deliver the batches to the customer. Each order has a weight, and the total weight of the orders packed in a batch must not exceed the capacity of the delivery batch. Each delivery batch incurs a fixed distribution cost. The problem is to find jointly a schedule for order processing and a way of packing completed orders to form delivery batches such that the total distribution cost (or equivalently, the number of delivery batches) is minimized subject to the constraint that a given customer service level is guaranteed. We consider two customer service constraints—meeting the given deadlines of the orders; or requiring the average delivery lead time of the orders to be within a given threshold. Several problems of the model with each of those constraints are considered. We clarify the complexity of each problem and develop fast heuristics for the NP‐hard problems and analyze their worst‐case performance bounds. Our computational results indicate that all the heuristics are capable of generating near optimal solutions quickly for the respective problems.     

A comparison of fixed and dynamic pricing policies in revenue management

We consider the problem of selling a fixed capacity or inventory of items over a finite selling period. Earlier research has shown that using a properly set fixed price during the selling period is asymptotically optimal as the demand potential and capacity grow large and that dynamic pricing has only a secondary effect on revenues. However, additional revenue improvements through dynamic pricing can be important in practice and need to be further explored. We suggest two simple dynamic heuristics that continuously update prices based on remaining inventory and time in the selling period. The first heuristic is based on approximating the optimal expected revenue function and the second heuristic is based on the solution of the deterministic version of the problem. We show through a numerical study that the revenue impact of using these dynamic pricing heuristics rather than fixed pricing may be substantial. In particular, the first heuristic has a consistent and remarkable performance leading to at most 0.2% gap compared to optimal dynamic pricing. We also show that the benefits of these dynamic pricing heuristics persist under a periodic setting. This is especially true for the first heuristic for which the performance is monotone in the frequency of price changes. We conclude that dynamic pricing should be considered as a more favorable option in practice.     

Assortment Planning for Vertically Differentiated Products

We consider the problem of a retailer managing a category of vertically differentiated products. The retailer has to pay a fixed cost for each product included in the assortment and a variable cost per product sold. Quality levels, fixed, and variable costs are exogenously determined. Customers differ in their valuation of quality and choose the product (if any) that maximizes their utility. First, we consider a setting in which the selling prices are also fixed. We find that the optimal set of products to offer depends on the distribution of customer valuations and might include dominated products, that is, products which are less attractive than at least one other product, on every possible dimension. We develop an efficient algorithm to identify an optimal assortment. Second, we consider a setting in which the retailer also determines the selling prices. We show that in this case the optimal assortment does not include any dominated product and does not vary with the distribution of customer valuations when there is no fixed cost. We develop several efficient algorithms to identify an optimal assortment and optimally price the products. We also test the applicability of our methods with realistic data for two product categories.     

OPTIMAL AND HEURISTIC SOLUTIONS FOR THE MULTI‐ITEM NEWSVENDOR PROBLEM WITH A SINGLE CAPACITY CONSTRAINT

This research considers a multi‐item newsvendor problem with a single capacity constraint. While this problem has been addressed in the literature, the focus here is on developing simple, closed‐form expressions for the order quantities. The benefit of such an approach is that the solutions are straightforward to calculate and have managerial appeal. Additionally, we show these expressions to be optimal under a variety of conditions. For more general cases when these optimality conditions do not hold, we use these expressions as heuristic solutions. Via computational studies, we demonstrate that these heuristics are extremely effective when the optimality conditions are not satisfied.     

Corporate structure optimisation for multinational companies

In this paper we consider a multinational corporate structuring problem. This problem involves designing a corporate/organisational structure (across different countries) so as to remit profits from a number of subsidiaries to a single parent company, whilst minimising the tax paid (maximise the amount received at the parent company). This corporate structure is constrained to be a (directed) tree structure.We present a mixed-integer zero-one formulation of the problem that (for the test problems examined) provides very good linear programming relaxation bounds. We also present a tabu search heuristic for the problem which, when combined with the bounds provided by the linear programming relaxation, is able to find provably optimal solutions. Extensions to the basic corporate structuring problem and how they can be dealt with using our heuristic are also discussed.Computational results for the solution (to proven optimality) of publicly available test problems involving up to 150 countries are reported. The largest problem solved previously in the literature to proven optimality involved only 22 countries.     

Scheduling two-stage production lines with multiple machines

Most manufacturing process maintain separate fabrication and assembly centres. Based on this observation, the author coincides a manufacturing process that contains two stages of production with multiple machines. The manufacturer produces a variety of products to satisfy customer demands, operates under a 'push' mode and in a ‘ make-to-order’ environment. Each customer order consists of known quantities of different products which must be delivered as a whole shipment. Periodically, the manufacturer schedules all the accumulated unscheduled customer orders. The scheduling objective is to minimize the sum of weighted customer order lead times. Such manufacturing systems are formulated as a mathematical programming problem. It is then shown that this problem is unary NP-hard and remains unary NP-hard even when all the weights are equal. Some insights about the structure of the optimal schedule(s) are provided and some special cases solved in polynomial time. Several polynomial time heuristics are proposed, and worst-case analysis of some of the heuristics are provided. Tight lower bounds are developed in order to measure the performance of the proposed heuristics. Numerical examples are presented and possible extensions are discussed.     

Determining Order Quantity and Selling Price by Geometric Programming: Optimal Solution,Bounds, and Sensitivity*

This paper presents a geometric programming (GP) approach to finding a profit-maximizing selling price and order quantity for a retailer. Demand is treated as a nonlinear function of price with a constant elasticity. The proposed GP approach finds optimal solutions for both no-quantity discounts and continuous quantity discounts cases. This approach is superior to the traditional approaches of solving a system of nonlinear equations. Since the profit function is not concave, the traditional approaches may require an exhaustive search, especially for the continuous discounts schedule case. By applying readily available theories in GP, we easily can find global optimal solutions for both cases. More importantly, the GP approach provides lower and upper bounds on the optimal profit level and sensitivity results which are unavailable from the traditional approaches. These bounding and sensitivity results are further utilized to provide additional important managerial implications on pricing and lot-sizing policies.     

On cutting stock with due dates

Classical stock cutting calls for fulfilling a given demand of parts, minimizing raw material needs. With the production of each part type regarded as a job due within a specific date, a problem arises of scheduling cutting operations. We here propose an exact integer linear programming formulation, and develop primal heuristics, upper bounds and an implicit enumeration scheme. A computational experience carried out for the one-dimensional problem shows that our primal heuristics outperform known ones, and that the formulation has good features for finding exact solutions of non-trivial instances.     

Revenue Management of Reusable Resources with Advanced Reservations

We consider a revenue management problem wherein the seller is endowed with a single type resource with a finite capacity and the resource can be repeatedly used to serve customers. There are multiple classes of customers arriving according to a multi‐class Poisson process. Each customer, upon arrival, submits a service request that specifies his service start time and end time. Our model allows customer advanced reservation times and services times in each class to be arbitrarily distributed and correlated. Upon arrival of each customer, the seller must instantaneously decide whether to accept this customer's service request. A customer whose request is denied leaves the system. A customer whose request is accepted is allocated with a specific item of the resource at his service start time. The resource unit occupied by a customer becomes available to other customers after serving this customer. The seller aims to design an admission control policy that maximizes her expected long‐run average revenue. We propose a policy called the ε‐perturbation class selection policy (ε‐CSP), based on the optimal solution in the fluid setting wherein customers are infinitesimal and customer arrival processes are deterministic, under the restriction that the seller can utilize at most (1 − ε) of her capacity for any ε ∈ (0, 1). We prove that the ε‐CSP is near‐optimal. More precisely, we develop an upper bound of the performance loss of the ε‐CSP relative to the seller's optimal revenue, and show that it converges to zero with a square‐root convergence rate in the asymptotic regime wherein the arrival rates and the capacity grow up proportionally and the capacity buffer level ε decays to zero.     

Late season low inventory assortment effects in the newsvendor problem

The assumption of the newsvendor being able to satisfy demand as long as on-hand inventory is positive does not hold for a non-homogenous product. Consumers who do not find a unit of the product which satisfies their secondary features preferences may not purchase the product even though the newsvendor has positive on-hand inventory. This is likely to occur late in the season as inventory level declines. We solve a newsvendor problem in which the probability of purchase by consumers is increasing in on-hand inventory for any inventory level below that which is needed to have a complete assortment. We identify the sufficient optimality condition for the order quantity. We show that, unlike the case of inventory-dependent demand models in the literature, the optimal order quantity may decrease due to the assortment effect. We investigate two types of pre-end of season discounts, immediate all-units and delayed, as ways to mitigate the late season assortment effect and show that in some cases, they can increase the newsvendor׳s profit and free up the shelf space for other products.