Authors:Xin Guo; Qiuli Liu; Yi Zhang Abstract: We consider a risk-sensitive continuous-time Markov decision process over a finite time duration. Under the conditions that can be satisfied by unbounded transition and cost rates, we show the existence of an optimal policy, and the existence and uniqueness of the solution to the optimality equation out of a class of possibly unbounded functions, to which the Feynman–Kac formula was also justified to hold. PubDate: 2019-01-10 DOI: 10.1007/s10288-019-0398-6
Authors:M. T. Alonso; R. Alvarez-Valdes; F. Parreño Abstract: We consider the multicontainer loading problem of a company that has to serve its customers by first putting the products on pallets and then loading pallets onto trucks. When a large number of units of a product have to be shipped, the company requires that homogeneous pallets, with only one product, are built first, then weakly heterogeneous pallets, in which each layer corresponds to a single product, and finally strongly heterogeneous pallets with the remaining units of the products. To be useful in practice, the solutions have to satisfy five types of constraints: geometric constraints, so that pallets are completely inside the trucks and do not overlap; weight constraints, limiting the total weight a truck can bear and the maximum weight supported by each axle; constraints limiting the position of the centre of gravity of the cargo; dynamic stability constraints, to avoid cargo displacement when the truck is moving; and constraints ensuring that the delivery dates of products are respected. We have developed a Greedy Randomized Adaptive Search Procedure, including some improvement methods tailored to the problem, among them an adaptation of ejection chains. The approach has been tested on a benchmark of real problems and it has been shown to be capable of finding high-quality, realistic solutions in short computing times. We also provide a comparison with an integer programming formulation that justifies the use of a metaheuristic algorithm. PubDate: 2019-01-01 DOI: 10.1007/s10288-018-0397-z
Authors:S. Nobakhtian; A. Raeisi Dehkordi Pages: 343 - 377 Abstract: In this paper, we consider a multi-source Weber problem of m new facilities with respect to n demand regions in order to minimize the sum of the transportation costs between these facilities and the demand regions. We find a point on the border of each demand region from which the facilities serve the demand regions at these points. We present an algorithm including a location phase and an allocation phase in each iteration for solving this problem. An algorithm is also proposed for carrying out the location phase. Moreover, global convergence of the new algorithm is proved under mild assumptions, and some numerical results are presented. PubDate: 2018-12-01 DOI: 10.1007/s10288-017-0366-y Issue No:Vol. 16, No. 4 (2018)
Authors:Xia Zhao; Runsheng Yin Pages: 379 - 400 Abstract: This paper investigates the coordination problem of a supply chain (SC) composed of a manufacturer exhibiting corporate social responsibility (CSR) and a retailer faced with random demand. The random demand is made up of the multiplication of price-dependent demand and random demand factor (RDF), plus the CSR-dependent demand. The centralized decision problem of the SC is an extension of the existing price setting newsvendor problem (PSNP). It is found that the sufficient condition for the quasi-concavity of expected profit (EP) on PSNP can not ensure the quasi-concavity of EP of the SC. Then, the concavity condition of EP related to the CSR effect factor is presented in the case of uniformly distributed RDF and linear demand in price, and the concavity of EP is proven under centralized decision. For decentralized decision under manufacturer’s Stackelberg game, the manufacturer determines wholesale price and its CSR investment, and then the retailer decides the order quantity and the retail price. The standard revenue-sharing (RS) contract is found not able to coordinate the SC, so a modified RS (MRS) contract is proposed to coordinate the SC. Finally, numerical examples illustrate the validity of the theoretical analysis and the coordination effectiveness of the MRS contract via Matlab. PubDate: 2018-12-01 DOI: 10.1007/s10288-017-0368-9 Issue No:Vol. 16, No. 4 (2018)
Authors:Luciana Casacio; Aurelio R. L. Oliveira; Christiano Lyra Pages: 401 - 410 Abstract: Interior point methods usually rely on iterative methods to solve the linear systems of large scale problems. The paper proposes a hybrid strategy using groups for the preconditioning of these iterative methods. The objective is to solve large scale linear programming problems more efficiently by a faster and robust computation of the preconditioner. In these problems, the coefficient matrix of the linear system becomes ill conditioned during the interior point iterations, causing numerical difficulties to find a solution, mainly with iterative methods. Therefore, the use of preconditioners is a mandatory requirement to achieve successful results. The paper proposes the use of a new columns ordering for the splitting preconditioner computation, exploring the sparsity of the original matrix and the concepts of groups. This new preconditioner is designed specially for the final interior point iterations; a hybrid approach with the controlled Cholesky factorization preconditioner is adopted. Case studies show that the proposed methodology reduces the computational times with the same quality of solutions when compared to previous reference approaches. Furthermore, the benefits are obtained while preserving the sparse structure of the systems. These results highlight the suitability of the proposed approach for large scale problems. PubDate: 2018-12-01 DOI: 10.1007/s10288-018-0370-x Issue No:Vol. 16, No. 4 (2018)
Authors:P. Stroobant; P. Audenaert; D. Colle; M. Pickavet Pages: 411 - 439 Abstract: In the context of recreational routing, the problem of finding a route which starts and ends in the same location (while achieving a length between specified upper and lower boundaries) is a common task, especially for tourists or cyclists who want to exercise. The topic of finding a tour between a specified starting and ending location while minimizing one or multiple criteria is well covered in literature. In contrast to this, the route planning task in which a pleasant tour with length between a maximum and a minimum boundary needs to be found is relatively underexplored. In this paper, we provide a formal definition of this problem, taking into account the existing literature on which route attributes influence cyclists in their route choice. We show that the resulting problem is NP-hard and devise a branch-and-bound algorithm that is able to provide a bound on the quality of the best solution in pseudo-polynomial time. Furthermore, we also create an efficient heuristic to tackle the problem and we compare the quality of the solutions that are generated by the heuristic with the bounds provided by the branch-and-bound algorithm. Also, we thoroughly discuss the complexity and running time of the heuristic. PubDate: 2018-12-01 DOI: 10.1007/s10288-018-0371-9 Issue No:Vol. 16, No. 4 (2018)
Authors:Sergio Consoli; Jan Korst; Gijs Geleijnse; Steffen Pauws Abstract: The minimum quartet tree cost (MQTC) problem is a graph combinatorial optimization problem where, given a set of \(n \ge 4\) data objects and their pairwise costs (or distances), one wants to construct an optimal tree from the \(3 \cdot {n \atopwithdelims ()4}\) quartet topologies on n, where optimality means that the sum of the costs of the embedded (or consistent) quartet topologies is minimal. The MQTC problem is the foundation of the quartet method of hierarchical clustering, a novel hierarchical clustering method for non tree-like (non-phylogeny) data in various domains, or for heterogeneous data across domains. The MQTC problem is NP-complete and some heuristics have been already proposed in the literature. The aim of this paper is to present a first exact solution approach for the MQTC problem. Although the algorithm is able to get exact solutions only for relatively small problem instances, due to the high problem complexity, it can be used as a benchmark for validating the performance of any heuristic proposed for the MQTC problem. PubDate: 2018-11-27 DOI: 10.1007/s10288-018-0394-2
Authors:Simon Bull; Jesper Larsen; Richard M. Lusby; Natalia J. Rezanova Abstract: The line planning problem that arises in the planning of a passenger railway involves selecting a number of lines from a potential pool to provide sufficient passenger capacity, meeting operational requirements, while optimising some measure of line quality. We model, and solve, the problem of minimising the average passenger system time, including frequency-dependent estimates for switching between lines in collaboration with Danish State Railways (DSB). We present a multi-commodity flow formulation for the problem of freely routing passengers, coupled to discrete line-frequency decisions selecting lines from a predefined pool. The performance of the developed methodology is analysed on instances taken from the suburban commuter network, DSB S-tog, in Copenhagen, Denmark. We show that the proposed approach yields line plans that are superior from both an operator and a passenger perspective to line plans that have been implemented in practice. PubDate: 2018-10-06 DOI: 10.1007/s10288-018-0391-5
Authors:Mariusz Górajski; Dominika Machowska Abstract: This paper examines the long-term impact of loyalty programs on a company’s profit and reputation among customers, and with different durations of product use. We analyze how the launch of loyalty programs may change the profitability of optimal advertising activities. The basis of this study is a modified goodwill model where the market is segmented according to usage experience. The main novelty is the role of loyalty programs and consumer recommendations in the creation of product goodwill, and also their influence on optimal advertising. The dynamics of goodwill are described by a partial differential equation. The firm maximizes the sum of discounted profits by choosing a different advertising campaign for each market segment. For a high-quality product, we observe that there is a trade off between the loyalty program and optimal advertising strategies. For a low-quality product, the loyalty program causes more profitable companies to invest heavily in additional advertising efforts. PubDate: 2018-10-05 DOI: 10.1007/s10288-018-0386-2
Authors:Amir Ahamdi-Javid; Nasrin Ramshe Abstract: Automated Guide Vehicles (AGVs) are widely used in material handling systems. In practice, to achieve more space utilization, safety, cost reduction, and increased flexibility, only a limited number of manufacturing cells may be preferred to have direct access to AGV travel paths, and the other cells are chosen to have no or indirect access to them. This paper investigates the problem of determining a single loop in a block layout with two criteria: loop length and loop-adjacency desirability. Unlike the traditional single shortest loop design problem, where all cells must be located next to the loop, the proposed problem considers a more realistic assumption that each cell in the block layout has a different preference with regard to being adjacent to the loop: some cells must be located adjacent to the loop, some must not be adjacent to the loop, and others can be located next to the loop but with different positive or negative priorities. The problem is formulated as a bi-objective integer linear programming model with two exponential-size constraint sets. A cutting-plane algorithm is proposed to solve the model under important methods commonly used to deal with a bi-objective model. The numerical results show the high efficiency of the proposed algorithm in large scales. PubDate: 2018-10-04 DOI: 10.1007/s10288-018-0383-5
Authors:Zohre Aminifard; Saman Babaie-Kafaki Abstract: Based on a singular value analysis conducted on the Dai–Liao conjugate gradient method, it is shown that when the gradient approximately lies in the direction of the maximum magnification by the search direction matrix, the method may get into some computational errors and also, the convergence may occur hardly. Hence, we obtain a formula for computing the Dai–Liao parameter which makes the direction of the maximum magnification by the search direction matrix to be orthogonal to the gradient. We briefly discuss global convergence of the corresponding Dai–Liao method with and without convexity assumption on the objective function. Numerical experiments on a set of test problems of the CUTEr collection show practical effectiveness of the suggested adaptive choice of the Dai–Liao parameter in the sense of the Dolan–Moré performance profile. PubDate: 2018-09-26 DOI: 10.1007/s10288-018-0387-1
Hybrid journal (It can contain Open Access articles)
[2352 journals]
