記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：PERGAMON-ELSEVIER SCIENCE LTD  

Electric vehicles have recently received considerable attention given their environmental and financial implications. This paper focuses on electric and diesel-powered vehicle routing, a vehicle routing problem targeted at electric and diesel-powered vehicles. We introduce the new concept of original graph, where various conditions such as inclines of roads, vehicle speed and acceleration are considered. Moreover, we formulate the problem as a mixed integer linear programming formulation. The results of simulations demonstrate the utility of the new model in the real world. (C) 2017 Elsevier Ltd. All rights reserved.

DOI： 10.1016/j.tre.2017.09.004

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：オペレーションズ・マネジメント＆ストラテジー学会  

Research in the field of scheduling has been undergoing a shift in recent years from a focus on nurse scheduling to that on service industry scheduling at hotels and restaurants. Reducing employment costs and figuring out how to put non-regular employments in place to cope with fluctuating demand are critical issues in this sector, particularly when it comes to the scheduling problem to the service industry that depends on human service providers. To cope with these challenges, this paper proposes a shift scheduling model that effectively takes into consideration non-regular employments specializing in food and beverage service in hotel restaurants. It also considers the use of two types of the non-regular employments who are called monthly staff and one-time staff with different working arrangements.

DOI： 10.20586/joms.6.1_17

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：IEEE COMPUTER SOC  

Electric vehicles have recently received attention due to the environmental and financial implication. However, they are still not popular because of their inconvenience; limited battery capacities and long recharge times. In order to grow popular of electric vehicles, several studies in the field of optimization have been engaged. One of the studies is routing problem for energy-optimized driving. In this paper, we deal with the electric and fuel-engined vehicle routing problem (EFVRP); this problem is a type of the vehicle routing problem where we use electric vehicles and fuel-engined vehicles (e.g. gasoline-powered vehicles). We model the EFVRP and propose a column generation approach for the EFVRP. Experiments compare the results obtained using our model and algorithm with their lower bounds.

DOI： 10.1109/SMC.2015.346

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：ELSEVIER SCIENCE BV  

A hypergraph F is a set family defined on vertex set V. The dual of F is the set of minimal subsets H of V such that F boolean AND H not equal phi for any F is an element of F. The computation of the dual is equivalent to several problems, such as minimal hitting set enumeration of a subset family, generation problem for maximal frequent and minimal infrequent sets, and so on. Although many algorithms have been proposed for the problem, to the best of our knowledge, none of them can work on large-scale input with a large number of minimal hitting sets. In this paper, we propose efficient algorithms for checking the minimality and pruning methods. These algorithms enable us to construct time effective and polynomial space dualization algorithms. The computational experiments show that our algorithms are quite fast even for large-scale input for which existing algorithms do not terminate in a practical time. (C) 2014 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2014.01.012

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：IEEE Computer Society  

The multi-vehicle covering tour problem (m-CTP) is defined on a graph G = (V ∪ W, E), where V is a set of vertices that can be visited and W is a set of vertices that must be covered but cannot be visited. Each vertex in V covers a subset of W. Given the costs of edges (v&lt
inf&gt
i&lt
/inf&gt
, v&lt
inf&gt
j&lt
/inf&gt
) ε E, the objective of the m-CTP is to obtain a set of total minimum cost tours on subset of V, while covering all v&lt
inf&gt
l&lt
/inf&gt
ε W by up to m vehicles. In this paper, we propose algorithms for the m-CTP using column generation approach. Computational experiments show that our algorithms outperform the existing algorithms.

DOI： 10.1109/CoASE.2014.6899457

Scopus

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：PERGAMON-ELSEVIER SCIENCE LTD  

Multi-chip module (MCM) substrates are designed for packing two or more semiconductor chips. On these substrates, there are open faults in the wiring, which are electrical disconnections. We must therefore test the substrates to detect open faults, and it is essential to establish an efficient method of testing them. One type of test method uses two probes. Two probes, each touching one edge (end) of an inter-chip wiring, are used to check for the presence of faults. Testing is complete when we have confirmed that no faults exist on the MCM substrate. The objective is to minimize the time to complete testing, that is, our aim is to design efficient routes for the two probes. In this paper, we propose a novel approach of formulating the routing problem as a shortest path problem with covering constraints (SPCC) and we also propose three algorithms for the SPCC. In computational experiments, we show that our formulation and algorithms outperform the existing method. (C) 2013 Elsevier Ltd. All rights reserved.

DOI： 10.1016/j.compeleceng.2012.12.020

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Society for Industrial and Applied Mathematics Publications  

A hypergraph F is a set family defined on vertex set V. The dual of F is the set of minimal subsets H of V such that F ∪ H ≠ for any F ∈ F. The computation of the dual is equivalent to many problems, such as minimal hitting set enumeration of a subset family, minimal set cover enumeration, and the enumeration of hypergraph transversals. In this paper, we introduce a new set system induced by the minimality condition of the hitting sets, that enables us to use efficient pruning methods. We further propose an efficient algorithm for checking the minimality, that enables us to construct time efficient and polynomial space dualization algorithms. The computational experiments show that our algorithms are quite fast even for large-scale input for which existing algorithms do not terminate in practical time.

DOI： 10.1137/1.9781611972931.1

Scopus

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：JAPAN SOC MECHANICAL ENGINEERS  

A multi-chip module substrate is designed for packing two or more semiconductor chips. On a substrate, there may exist two types of faults; one in a wiring and the other at an intersection of two wires, called via, and the faults must be detected. The testing is performed by a pair of probes, which touch the two ends of an inter-chip wiring. The completion time of the whole testing is the time when it has been confirmed that no fault exists on the substrate. A two-probe routing problem is considered to design efficient routes of the two probes for minimizing the completion time of the whole testing. In this paper, the two-probe routing problem is formulated as a constrained shortest path problem, and a heuristic algorithm by local search techniques is proposed. Computational experiments demonstrate that the proposed heuristic algorithm outperforms a known two-phase heuristic.

DOI： 10.1299/jamdsm.7.644

Web of Science

researchmap

掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.20586/joms.5.1_74

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：IEEE  

Printed circuit boards (PCBs) are designed for packing two or more semiconductor chips. On these PCBs, there are various types of faults in the wiring. We must therefore test the PCBs to detect these faults, and it is essential to establish an efficient testing method. One type of test method uses two probes. Two probes, each touching one edge (end) of an inter-chip wiring, are used to check for the presence of faults. Testing is complete when we have confirmed that no faults exist on the PCB. The objective is to minimize the completion time for the testing, that is, our aim is to design efficient routes for the two probes; this is a two-probe routing problem. Several previous studies have proposed an approach involving a two-phase method. Although the two-phase method quickly finds a feasible solution, there is no guarantee that the solution is good. Besides, in recent years, PCB technology provides dense assembly capability and increased chip packaging; this implies that the scale of the two-probe routing problem becomes larger and the problem is difficult to be solved. We therefore propose a new approach, where we formulate a two-probe routing problem as a combinatorial optimization problem and then, we solve the combinatorial optimization problem by using genetic algorithm. We expect that our approach is useful for solving the large-scale problems. In computational experiments, we compare the results of our approach with those obtained using the two-phase method, and we show that our approach outperforms the two-phase method.

DOI： 10.1109/CEC.2012.6253012

Web of Science

researchmap

掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：IEEE  

Multi-chip module (MCM) substrate is designed to pack two or more semiconductor chips. On a MCM substrate, there might exist a few types of faults in the wiring. Thus, it is essential to establish an efficient method for testing in MCM to detect faults. This paper presents a heuristic algorithm for substrates testing in MCM. Our objective is to minimize the completion time of the testing. The testing is performed by two equipments, called probe. Several previous works propose a method for the testing. Although the method finds at least one feasible solution fast, there is no guarantee that the solution is always good. Therefore, we formulate a testing problem as a shortest path problem with covering constraints (SPCC) and then, we propose a heuristic algorithm for the SPCC. In computation experiments, we show the SPCC approach are superior to the existing method.

DOI： 10.1109/IEEM.2011.6117891

Web of Science

researchmap

掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

記述言語：英語   出版者・発行元：バイオメディカル・ファジィ・システム学会  

We examine a technique for solving the scheduling problem in the flexible flow shop, where the processing time is uncertain. The conventional scheduling method for the flexible flow shop is usually based on afirst-in-flrst-out rule at each stage. However, there is no guarantee that a good solution can be obtained by this method, especially because of the uncertain processing time. In the present study, we attempt to develop a scheduling method that provides a robust schedule against uncertainty in the processing time. In the present paper, we consider a procedure by which to generate robust schedules depending on the degree of uncertainly.

DOI： 10.24466/ijbschs.15.1_45

researchmap

掲載種別：研究論文（学術雑誌）  

DOI： 10.1299/kikaic.76.3220

researchmap

記述言語：日本語   掲載種別：研究論文（学術雑誌）   出版者・発行元：公益社団法人 日本経営工学会  

本論文は配送計画問題において顧客の需要量が不確実な状況を考えている.このような問題には,配送距離の期待値を最小するアプローチや,ルートのロバスト性を保持するアプローチなどが提案されている.期待値が最小になるアプローチによる配送計画は,よい結果を出す可能性が高い.しかしリスクを避けたい状況において,このアプローチを用いると最悪の場合の保証が得られず許容範囲外の悪い結果を出すことも考えられる.そこで本論文では最悪の場合を保証しなければならない状況を想定してロバストアプローチを用いる.ここでのロバストな配送計画とは配送前の計画通りに配送できる計画を指す.この問題を集合被覆問題で定式化して列生成法を用いて解くことでロバストな配送計画を求める.

DOI： 10.11221/jima.60.289

CiNii Books

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）  

The vehicle routing problem with stochastic demand (VRPSD) is one of the most important problems in distribution and transportation. The classical models for the vehicle routing problem with stochastic demand are the chance-constrained model and the penalty model. This paper proposes the hybrid model which combines the chance-constrained model and the penalty model. The travel cost of the hybrid model is less than that of the chance-constrained model and the worst case is guaranteed though the hybrid model may have more travel cost than the penalty model. We formulate the VRPSD as a set covering problem and this problem is solved using a column generation approach. We propose the solution methods for the hybrid model. The solution method is based on saving algorithm. In numerical results, we compare the results of the chance-constrained model, the penalty model and the hybrid model. © 2010 Inderscience Enterprises Ltd.

DOI： 10.1504/IJAMS.2010.033566

Scopus

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）  

researchmap

掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

開催年月日： 2008年9月

記述言語：日本語  

researchmap

開催年月日： 2006年9月

記述言語：日本語  

researchmap

開催年月日： 2005年

記述言語：日本語  

We examine the technique for solving the scheduling problem in the flexible flow shop where processing time is uncertain. The conventional scheduling method for flexible flowshop is usually based on first out first in rule on each stage. However, there is no guarantee that a good solution can be obtained by this method, especially for the uncertain processing time. Then, in this study, we consider to express the distribution of uncertain processing time with a normal distribution. Then, we aim to develop the scheduling method which provides a robust solution to the change of the degree of uncertainty.

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap