Open Access. Powered by Scholars. Published by Universities.®

Operations Research, Systems Engineering and Industrial Engineering Commons

Open Access. Powered by Scholars. Published by Universities.®

Articles 1 - 3 of 3

Full-Text Articles in Operations Research, Systems Engineering and Industrial Engineering

Pickup And Delivery Problem With Time Windows: Algorithms And Test Case Generation, Hoong Chuin Lau, Zhe Liang Sep 2002

Pickup And Delivery Problem With Time Windows: Algorithms And Test Case Generation, Hoong Chuin Lau, Zhe Liang

Research Collection School Of Information Systems

In the pickup and delivery problem with time windows (PDPTW), vehicles have to transport loads from origins to destinations respecting capacity and time constraints. In this paper, we present a two-phase method to solve the PDPTW. In the first phase, we apply a novel construction heuristics to generate an initial solution. In the second phase, a tabu search method is proposed to improve the solution. Another contribution of this paper is a strategy to generate good problem instances and benchmarking solutions for PDPTW, based on Solomon' s benchmark test cases for VRPTW. Experimental results show that our approach yields very ...


Integrating Local Search And Network Flow To Solve The Inventory Routing Problem, Hoong Chuin Lau, Q Liu, H. Ono Jul 2002

Integrating Local Search And Network Flow To Solve The Inventory Routing Problem, Hoong Chuin Lau, Q Liu, H. Ono

Research Collection School Of Information Systems

The inventory routing problem is one of important and practical problems in logistics. It involves the integration of inventory management and vehicle routing, both of which are known to be NP-hard. In this paper, we combine local search and network flows to solve the inventory management problem, by utilizing the minimum cost flow sub-solutions as a guiding measure for local search. We then integrate with a standard VRPTW solver to present experimental results for the overall inventory routing problem, based on instances extended from the Solomon benchmark problems.


A New Approach For Weighted Constraint Satisfaction, Hoong Chuin Lau Apr 2002

A New Approach For Weighted Constraint Satisfaction, Hoong Chuin Lau

Research Collection School Of Information Systems

We consider the Weighted Constraint Satisfaction Problem which is an important problem in Artificial Intelligence. Given a set of variables, their domains and a set of constraints between variables, our goal is to obtain an assignment of the variables to domain values such that the weighted sum of satisfied constraints is maximized. In this paper, we present a new approach based on randomized rounding of semidefinite programming relaxation. Besides having provable worst-case bounds for domain sizes 2 and 3, our algorithm is simple and efficient in practice, and produces better solutions than some other polynomial-time algorithms such as greedy and ...