出版者・発行元：Scheduling Society of Japan  

In this paper, we consider a robust p-hub median problem where the OD (origin-destination) flow is unknown. The majority of hub location models in the literature assume that all data are deterministic and known; however, the hub location decision should be made from a strategic perspective considering future demand change because it costs a lot of money to change later. From these observations, we apply robust optimization approach to the fundamental p-hub median problem that is the basis of various hub location models proposed in the last three decades. The numerical examples using two data sets including commonly used CAB data set show a rather small impact on the hub network structures.

出版者・発行元：南山大学  

クォータ制を導入した大学における授業の教師割り当てを求める問題を0-1整数計画問題として定式化し, 南山大学の授業データを用いて計算実験を行った. その結果, 1クォータ分の教室割り当てを約2秒で求めることができた. 手作業による教室割り当て作業には2 クォータ分で35時間程度を要していることから, 提案するモデルを用いることによって大幅に作業時間を削減できる可能性があることを示した.

The management of the automobile industry has changed recently because of the influence of the financial crisis and the industrial boom in developing countries such as Brazil, Russia, India, and China (BRICs). In this paper, we consider a global automobile-production optimization problem (GAPOP), which we model as a mixed integer programming (MIP) problem. The GAPOP determines global production bases and transportation plans to minimize the total cost of production, transportation, and facilities. It is a unified model that contains the facility location, production planning and transportation problems. We analyze the model for instances generated from real-world data with up to 20 production bases and 133 importing countries for the 18 years from 1997 to 2014. The computational results show that near-optimal solutions to our model are close to the present real-world situation. We also analyze our model with various parameter settings and observe from the results that, at each production base, changes in the number of production lines are affected mainly by labor and material costs. In addition, the proportion of each automobile type when allocating production is influenced by the material costs of all automobile types and the demands of nearby importing countries. Our model is expected to be of use to the automobile industry for making forecasts.

出版者・発行元：Scheduling Society of Japan  

In this paper, we consider a large-sized parking lot packed with vehicles in which all the vehicles leave there almost simultaneously. We propose a mathematical model to obtain a schedule for each leaving vehicle so as to minimize the time till the last vehicle leaves the parking lot. The schedule is presented by specifying a position of each vehicle by time unit. Such a system optimization solution may not be acceptable for individuals; however, it may give us a finding to
control traffic flows and design an efficient layout, which leads to reduce congestion in a parking lot.

出版者・発行元：Scheduling Society of Japan  

In this paper, we consider a point-to-point based airline network design problem (PPANP) in which a route connecting two nodes are set-up one by one without assuming a priori a hub structure. The majority of hub location models in the literature often implicitly ignore carriers' profitability as well as passengers' perspectives. The proposed model takes into account both factors in order to find a better airline networks for both carriers and passengers.

出版者・発行元：Scheduling Society of Japan  

In this paper, we consider a product shipping problem (PSP). Given a period and a set of products, each with a weight, a release date, and a due date, the PSP calls for product shipping to be planned between a fixed origin–destination pair so as to minimize the total shipping cost. Given several types of boxes with different sizes and shipping costs, packing several products into one larger box may lead to cheaper shipping costs than sending them separately in smaller boxes. The online PSP is a problem with an online constraint that requires a decision to be made for each day without knowing about future requests or being able to change boxes that have already been packed and shipped. For the online PSP, we propose column-generation-based algorithms with six different criteria incorporating ideas such as iterative surplus reduction and heuristic column generation. Computational results show that the proposed algorithms with one of the six criteria called “regret with cost of remaining capacity” obtain high-quality solutions with average gaps about 3% over all the tested instances.

出版者・発行元：The Japan Society of Mechanical Engineers  

In this paper, we consider a multi-hop sensor network, where the network topology is a tree, TDMA (time division multiple access) is employed as medium access control, and all data generated at sensor nodes are delivered to a sink node (the base station) located on the root of the tree through the network. It is reported that if a transmission schedule that avoids interference between sensor nodes completely can be computed, TDMA is preferable to CSMA/CA (carrier sense multiple access with collision avoidance) in performance. In general, the TDMA scheduling problem to find the shortest schedule is formulated as a combinatorial optimization problem, where each combination corresponds to a schedule. However, solving such a combinatorial optimization problem is difficult, especially for large-scale multi-hop sensor networks. The reason of the difficulty is that the number of the combinations increases exponentially with the increase of the number of nodes. In this paper, to formulate the TDMA scheduling problem, we propose a min-max model and a min-sum model. The min-max model yields the shortest schedule, but it is difficult to solve large-scale problems. The min-sum model does not guarantee providing the shortest schedule; however, it may give us good schedules over a short amount of computation time, compared to the min-max model. Numerical examples show that the min-sum model can provide good schedules in a reasonable CPU time, even when the min-max model fails to compute the shortest schedule in a reasonable CPU time.

出版者・発行元：南山大学  

本研究では, 路線の開設と廃止を考慮したポイント・トゥ・ポイント型航空ネットワーク設計モデルを提案する. 従来のハブ・アンド・スポーク型ネットワークにおいては, 拠点となるハブ空港を設置し, ハブ空港を発着点とする路線を展開することが前提である. ハブ・アンド・スポークネットワークを採用することによって, 広範囲に点在する需要を効率よく獲得できる一方で, 乗客にとっては乗り換え回数が増えるというデメリットもある. これを解消するために, 近年では, ハブ空港を設置せずにポイント・トゥ・ポイント型のサービスを展開する航空会社も存在する. 本研究で提案するモデルは, 従来のハブ・アンド・スポーク型のネットワークとは異なり, ハブ空港の設置は前提とせず, 利用者の増加が見込まれる路線の開設と採算の取れなくなった路線の廃止を繰り返すことによって航空ネットワークを構築する. さらに, 乗り換えによって生じる迂回距離を考慮した乗り換えコストを導入する. 計算実験の結果, 提案するモデルから得られる最適ネットワークにおいて, ハブ空港の役割を果たす空港が現れる例が見られることを示す. また, 乗り換えコストが最適なネットワークに大きな影響を与えることも示す.

This paper considers a strip packing problem with rectangles that are flexible in their dimensions, but fixed in their area. We generalize the best-fit heuristic, a well-known algorithm to solve the strip packing problem for rectangles of fixed sizes, investigating a set of simple heuristic rules with some modifications of the original rules. We also propose data structures to improve the efficiency of the resulting algorithms. The obtained solutions are evaluated on a set of 22; 500 randomly generated instances. Our approach provides good solutions, with an occupation ratio of more than 96% on average, for instances with flexible rectangles.

In this paper, we consider a scheduling problem of locating EV battery charging stations where the location of all stations to be installed eventually is given. Due to budgetary limitation, it might be generally difficult to install all stations at a time. In such a case, the stations would be located in order according to a pre-determined schedule. We propose a greedy heuristic method to find good schedules in reasonable time, and show some results using real data in Tokai region.

出版者・発行元：The City Planning Institute of Japan  

Recent years, in Japan supply insufficiency of medical service becomes important issue caused by aging society. Public services such as ambulance service are required to serve as equitably and efficiently as possible. For measuring or comparing sufficiency of service, supply quantity per capita and/or per area is generally used. This kind of indices is suitable for regions which are large enough to be considered as uniform density. In this paper, we propose an index representing supply-and-demand gap, which is generalization of supply sufficiency above. Then, we discuss features of proposed index considering numerical examples and iterative procedure how to calculate it. Finally, we adapt it to numbers of beds of acute hospitals in Kanagawa Prefecture, and visualize it.

出版者・発行元：Elsevier  

In this paper, we consider the design of large-scale multiple allocation hub-and-spoke transportation networks in a competitive environment. We adopt a generic hub arc location model that locates arcs with discounted transport costs connecting pairs of hub facilities. Two firms compete for customers in a Stackelberg framework where the leader firm locates hub arcs to maximize its revenue, given that the follower firm will subsequently locate its own hub arcs to maximize its own revenue. We present an optimal solution algorithm that allocates traffic between the two firms based on the relative utility of travel via the competing hub networks. Results for each competing firm with up to three hub arcs show the important role of competition in designing hub-based transportation systems.

出版者・発行元：日本オペレーションズ・リサーチ学会  

出版者・発行元：南山大学  

本研究では, 病院と患者の需給関係について地域格差が生じていることを可視化し, 地域や疾病によらず公平な医療サービスを受けられる体制を整えるためには, どの地域にどの程度の規模の医療施設が必要であるかに関する指標を作る. そのために, ここ数年で患者数の多かった呼吸器, 循環器, 消化器, 筋骨格系の4疾病を対象に, 既存病院間において生じている患者数のアンバランスを視覚化し, それぞれの入院患者数(需要)と対応する診療科の病床数(供給)を考慮した2つの新規病院配置モデル(単科病院配置モデル, 総合病院配置モデル)を提案する. はじめに, 患者は最近隣の病院を選択すると仮定して, 患者を既存病院へ割り当て, 各病院に割り当てられた患者数から既存病院間で生じた患者数の偏りを明らかにする. 次に, 提案する2つのモデルを用いて, 現状の需給バランスを解消する指標を求める. 単科病院配置モデルでは, 既存の総合病院だけでは供給が不十分である疾病に対する診療科を持つ単科病院の最適配置を求める. 総合病院配置モデルでは, 前述の4つの疾病に対応する診療科をすべて有する標準的な規模の総合病院の最適配置を求める.

One of the important issues in wireless sensor networks is how to save power consumption and extend the network lifetime. For this purpose, various network topology construction algorithms have been studied. However, most of them are based on a method repeating single round optimization. In other words, by considering the energy dissipation of sensor nodes only in the next round, a network topology in the next round is constructed in a round-by-round manner. The set of the topology constructions based on such a round-by-round view may be far from the optimal solution to maximize the network lifetime. To address this issue, we take the energy dissipation of sensor nodes over multiple rounds into account, and we consider the problem as a multi-dimensional knapsack problem, which enables us to find optimal network topologies until at least one sensor node exhausts its battery power. We also propose a solution method to maximize the network lifetime. The computational experiments show that the proposed approach provides
efficient topology construction in the wireless sensor network in terms of network lifetime compared to the cluster-based approach.

出版者・発行元：Wiley Periodicals, Inc  

This article describes a node capacitated in-tree packing problem. The input consists of a directed graph, a root node, a node capacity function, and edge consumption functions. The problem is to find the maximum number of rooted in-trees, such that the total consumption of in-trees at each node does not exceed the capacity of the node. The problem is one of the network lifetime problems that are among the most important issues in the context of sensor networks. We establish the computational complexity of the problem under various restrictions on consumption functions and graphs. For example, we consider general graphs, acyclic graphs, and complete graphs embedded in the d -dimensional space R^d having edge consumption functions depending only on distances between end nodes.

In this paper, we deal with the node capacitated in-tree packing problem. The input consists of a directed graph, a root node, a node capacity function and edge consumption functions for heads and tails. The problem is to find a subset of rooted spanning in-trees and their packing numbers, where the packing number of an in-tree is the number of times it is packed, so as to maximize the sum of packing numbers under the constraint that the total consumption of the packed in-trees at each node does not exceed the capacity of the node. This problem is known to be NP-hard.

We propose a two-phase heuristic algorithm for this problem. In the first phase, it generates candidate spanning in-trees to be packed. The node capacitated in-tree packing problem can be formulated as an IP (integer programming) problem, and the proposed algorithm employs the column generation method for the LP (linear programming) relaxation problem of the IP to generate promising candidate in-trees. In the second phase, the algorithm computes the packing number of each in-tree. Our algorithm solves this second-phase problem by first modifying feasible solutions of the LP relaxation problem and then improving them with a greedy algorithm. We analyze upper and lower bounds on the solution quality of such LP-based algorithms for this problem.

We conducted computational experiments on graphs used in related papers and on randomly generated graphs. The results indicate that our algorithm has a better performance than other existing methods.

出版者・発行元：南山大学  

本論文では，汎用性を重視した大学の時間割編成モデルを提案する．提案するモデルでは，各大学や学部に固有の複雑な制約条件を簡単に記述するための枠組みとして時間割編成を行う科目をグループ化する手法を用いる．目的に応じて科目を適切にグループ化することにより，さまざまな要求に応える時間割の作成が可能である．たとえば，教職課程等の選択コース履修者や再履修者に配慮した時間割を作成できる．また，本モデルでは，オムニバス科目等の開講形態が不規則な科目も自動編成の対象とし，教員の担当授業数の上下限を設定して自動的に授業担当者を割り当てることも可能である．南山大学情報理工学部の2012 年度時間割実データを用いた計算実験により，実用的な時間で時間割を作成し，出力できることを示す．

In this paper, we consider a multi-hop wireless sensor network, where the network topology is a tree, time division multiple access (TDMA) is employed as medium access control, and all data generated at sensor nodes are delivered to a sink node located on the root of the tree through the network. It is reported that if a transmission schedule that avoids interference between sensor nodes completely can be computed, TDMA is preferable to others in performance. However, solving the scheduling problem for TDMA is difficult, especially, in large-scale multi-hop sensor networks. In this paper, we propose a new formulation of the scheduling problem by TDMA based on graph theory.

In this paper, we consider a multi-hop sensor network, where the network topology is a tree, TDMA is employed as medium access control, and all data generated at sensor nodes are delivered to a sink node located on the root of the tree through the network. It is reported that if a transmission schedule that avoids interference between sensor nodes completely can be computed, TDMA is preferable to CSMA/CA in performance. However, solving the scheduling problem for TDMA is difficult, especially, in large-scale multi-hop sensor networks. In this paper, to formulate the scheduling problem for TDMA, we propose min-max model and min-sum model. While the min-max model yields the shortest schedule under the constraints, the min-sum model does not guarantee providing the shortest schedule. Numerical examples show that the min-sum model can provide good schedules in a reasonable CPU time, even when the min-max model fails to compute the shortest schedule in a reasonable CPU time.

出版者・発行元：The Operations Research Society of Japan  

In this paper, we study mathematical formulations for clustering problems which arise in wireless sensor networks as examined from the standpoint of facility location theory. Following facility location theory, LEACH-C, one of the principal studies on cluster-based network organizations, formulates the clustering problem as a p-median problem. In this paper, we examine some drawbacks to the formulation put forward in LEACHC. We then formulate the problem as an uncapacitated facility location problem to overcome these drawbacks. Computational experiments show that compared to LEACH-C, the proposed algorithm based on our formulation
can extend the total lifetime of sensor networks.

In this paper, we proposed a two-phase heuristic algorithm for the node capacitated in-tree packing problem. In the first phase, it generates candidate in-trees to be packed employing the delayed column generation method for the LP-relaxation of the problem. We showed that solving the pricing problem is equivalent to solving the minimum weight rooted arborescence problem. In the second phase, the algorithm computes the packing number of each in-tree by first modifying feasible solutions of the LP-relaxation problem and then improving them with a greedy algorithm. We proposed an efficient data structure that makes use of the properties of the evaluation criteria. The proposed algorithm obtains solutions that are close to the upper bounds and is proved to be effective for this problem.

出版者・発行元：World Publishing Coroporation  

In this paper, we consider the design of airline network in Asia where optimal locations of the gateways and local hubs are established. We report some results using the demand data reported by IATA in 2005. The results show interesting features of gateway locations in Asia.

出版者・発行元：Nanzan University  

In this paper, we consider the design of large-scale hub-and-spoke transportation networks in a competitive environment. We adopt the hub arc location model that locates arcs with discounted transport costs connecting pairs of hub facilities. Two firms compete for customers in a Stackelberg framework where the leader firm locates hub arcs to maximize its revenue, given that the follower will subsequently locate its own hub arcs to maximize its own revenue. Several mechanisms are presented to allocate traffic between the two firms based on the relative utility of travel via the competing hub networks. Results with up to three hub arcs for each competing rm show the role of a competitive environment in designing transportation systems.

出版者・発行元：東京大学工学部計数工学科  

This paper describes a node capacitated in-tree packing problem. The input consists of a directed graph, a root node, a node capacity function and edge consumption functions. The problem is to find the maximum number of rooted in-trees such that the total consumption of in-trees at each node does not exceed the capacity of the node. The problem is one of the network lifetime problems that are among the most important issues in the context of sensor networks. We reveal the computational complexity of the problem under various restrictions on consumption functions and graphs. For example, we consider general graphs, acyclic graphs and complete graphs embedded in the d-dimensional space Rd having edge consumption functions depending only on distances between end nodes.

In this paper, we deal with the node capacitated in-tree packing problem. The input consists of a directed graph, a root node, a node capacity function and edge consumption functions for heads and tails. The problem consists of finding the maximum number of rooted in-trees such that the total consumption of the in-trees at each node does not exceed the capacity of the node. This problem is known to be NP-hard. We propose a two-phase heuristic algorithm for this problem. In the first phase, it generates candidate in-trees to be packed. The node capacitated in-tree packing problem can be formulated as an IP (integer programming) problem, and the proposed algorithm employs the delayed column generation method for the LP (liner programming)-relaxation problem of the IP to generate promising candidate in-trees. In the second phase, the algorithm computes the packing number of each in-tree. Our algorithm solves this second-phase problem by first modifying feasible solutions of the LP-relaxation problem and then improving them with a greedy algorithm. We conducted computational experiments on graphs used in related papers and on randomly generated graphs. The results indicate that our algorithm has a better performance than other existing methods.

出版者・発行元：International Conference on Industrial Engineering and Systems Management  

In this paper, we consider the design of large-scale hub-and-spoke transportation networks in a competitive environment. We adopt the hub arc location model that locates arcs with discounted transport costs connecting pairs of hub facilities. Two firms compete for ustomers in a Stackelberg framework where the leader firm locates hub arcs to maximize its revenue, given that the follower rm will subsequently locate its own hub arcs to maximize its own revenue. Two mechanisms are presented to allocate traffic between the two firms based on the relative utility of travel via the competing hub networks. Results with up to three hub arcs for each competing firm show the role of a competitive environment in designing transportation systems.

出版者・発行元：International Network Optimization Conference  

In this paper, we deal with a node capacitated in-tree packing problem. The input consists of a directed graph, a root node, a node capacity function and edge consumption functions. The problem is to find the maximum number of rooted in-trees such that the total consumption of in-trees at each node does not exceed the capacity of the node. The problem is one of the network lifetime problems that are among the most important issues in the context of sensor networks. We reveal the computational complexity of the problem under various restrictions on consumption functions and graphs. For example, we consider general graphs, cyclic graphs and complete graphs embedded in the d-dimensional space Rd having edge consumption functions depending on distances between end nodes.

出版者・発行元：IFORS  

We consider hierarchical facility location problems on a network called MLTP and FTPLP, where q facilities and p transfer points are located and each customer goes to one of the facilities directly or via one of the transfer points. In FTPLP, we need to find an optimal location of both the facilities and the transfer points while the location of facilities is given in MLTP. Although good heuristics have been proposed for the minisum MLTP and FTPLP, no exact optimal solution has been tested due to the size of the problems. We show that the minisum MLTP can be formulated as a p-median problem, which leads to obtaining an optimal solution. We also present a new formulation of FTPLP and an enumeration-based approach to solve the problems with a single facility.

出版者・発行元：日本OR学会常設研究部会数理計画(RAMP)  

One of crucial challenges in organizing wireless sensor networks is energy efficiency. For this purpose, various topology construction methods to save power consumption of sensors and extend the network lifetime have been studied. In this paper, we show that these topology construction problems can be formulated as optimization problems such as facility location problems, and introduce how we apply an optimization approach to the topology construction problems. From the computational experiments, we show that an optimization approach brings better solutions in terms of network lifetime compared to those studied so far.

出版者・発行元：Institute of Intelligent Information and Communications Technology, Konan University  

One of the important issues in wireless sensor networks is how to save power consumption and extend the network lifetime. For this purpose, various network topology construction algorithms have been studied. However, most of them are based on a myopic method, where the topology construction is carried out round-by-round. To address this issue, we take the energy dissipation of sensor nodes over multiple rounds into account, and we consider the problem as a multi-dimensional knapsack problem, which enable us to find optimal network topologies until at least one sensor node exhausts its battery power. We also propose a solution method to maximize the network lifetime.The computational experiments show that the proposed approach provides efficient topology construction in the wireless sensor network in terms of network lifetime compared to the cluster-based approach.

出版者・発行元：Nanzan University  

One of the important issues in wireless sensor networks is how to save power consumption and extend the network lifetime. For this purpose, various network topology construction algorithms have been studied. However, most of them are based on a myopic method, where the topology construction is carried out round-by-round. To address this issue, we take the energy dissipation of sensor nodes over multiple rounds into account, and we consider the problem as a multi-dimensional knapsack problem, which enable us to find optimal network topologies until at least one sensor node exhausts its battery power. We also propose a solution method to maximize the network lifetime.The computational experiments show that the proposed approach provides efficient topology construction in the wireless sensor network in terms of network lifetime compared to the cluster-based approach.

出版者・発行元：IEEE  

We present a new heuristic method for a clustering problem of sensor networks. The heuristic method is using the uncapacitated facility location problem formulation for the clustering problem of sensor networks. It is an iterative method based on the Voronoi diagram. We also propose a parallel version of the heuristics to reduce the time to obtain a solution. By comparing the approximate solutions to the exact solutions for examples of one hundred sensors, we found that the quality of the approximate solutions is almost the same as that of the exact ones. The computational time to obtain the approximate solutions is a thousandth of that of obtaining the exact solution. For examples of ten thousand sensors, the computational time is about 9.1 seconds by the sequential algorithm and about 6.0 seconds by our parallel algorithm with six computers.

出版者・発行元：Nanzan University  

In this paper, we study clustering algorithms for wireless sensor networks from a view of facility location theory. From this view, we can consider that LEACH-C, which is one of the principal studies on cluster-based network organization, formulates the clustering problem as a p-median problem. We point out drawbacks of the formulation in LEACH-C. To overcome the drawbacks, we formulate the problem as an uncapacitated facility location problem. Computational experiments show that the proposed algorithm can extend the lifetime of sensor networks, compared to LEACH-C.

出版者・発行元：南山大学  

対象地域から特定の別の地域への国際旅客需要を考慮したゲートウェイ空港の最適配置モデルを提案する．また，IATA(International Air Transport Association)が発表した2005年のODデータを用いて行ったアジア地域における最適ゲートウェイを求める数値実験の結果を紹介する．

出版者・発行元：Nanzan University  

We consider hierarchical facility location problems on a network called MLTP and FTPLP, where q facilities and p transfer points are located and each customer goes to one of the facilities directly or via one of the transfer points. In FTPLP, we need to find an optimal location of both the facilities and the transfer points while the location of facilities is given in MLTP. Although good heuristics have been proposed for the minisum MLTP and FTPLP, no exact optimal solution has been obtained due to the size of the problems. We show that the minisum MLTP can be formulated as the p-median problem, which leads us to obtain an optimal solution. We also present a new formulation of FTPLP and an enumeration-based approach to solve the problems with a single facility.

出版者・発行元：南山大学  

本論文では，中継点と施設の2つの階層を持つ階層型施設配置モデルMLTPおよびFTPLPを扱う．ミニサム型MLTPがpメディアン問題に帰着できることを示し，一般化モデルであるFTPLPに対するフロー型の新しい定式化を提案する．計算機実験では，これまで求められなかったミニサム型MLTPおよびFTPLPの厳密解を求める．

出版者・発行元：南山大学  

We consider a statistical approach to decide specifications of center console of automobiles. The design of the center console is an important part in the sense that it has a strong effect for user satisfaction. From this standpoint, the center console should be adequately designed. However, the design process usually relies on a trial and error approach, which consumes lots of time. If the relationships between usability and physical specifications are revealed, we may design the center console with higher user satisfaction in a shorter time. For this purpose, we carry out a questionnaire survey. The results show several interesting relationships.

出版者・発行元：The Operations Research Society of Japan  

We consider a hub network design model based on the Stackelberg hub location model, where two firms compete with each other to maximize their own profit. The firm as a leader first locates p hubs and decides which OD pairs should be in services on the condition that the other firm as a follower locates q hubs and decides its strategies in a similar way after that. To avoid the possibility of unprofitable services, we incorporate flow threshold constraints into the model. We formulate the leader's problem as a bilevel programming problem with the follower's problem as a lower level problem. We solve the problem with the complete enumeration method and a greedy heuristic. The main objective is to make it clear how the network structurecan be affected by the flow threshold constraints and the competitor's strategies.

出版者・発行元：Nanzan University  

自動車のセンターコンソールを設計するための定量的アプローチを提案するために，ユーザに対して行ったアンケートの結果およびセンターコンソールを構成するボタンやスイッチの物理量の計測結果を分析して報告する．

出版者・発行元：Nanzan University  

競枝流量下限制約のある競合型ハブネットワークデザインモデルを提案し，流量制約の変化が解に与える影響を分析する．

出版者・発行元：南山大学  

競合を考慮したハブ配置モデルとして提案されているシュタッケルベルグ型ハブ配置モデルに改良を加え, 新しくハブ・ネットワークデザインモデルを構築する．実用性の観点から重要な要素とされる枝流量下限制約を設け，ハブと枝の配置およびODペアごとの運航ルートを同時に求める総合的なネットワーク設計を行うモデルの構築を目指す．

出版者・発行元：京都大学  

Throughout the dissertation, we focus on the hub location models which belong to the one-stop class. We consider various types of those models and develop both exact and heuristic methods to solve the problems. Moreover, we examine how the optimal hub locations are afected by various constraints and consider important factors to develop a model for the more practical use.

出版者・発行元：The Operations Research Society of Japan  

In this paper, we present a new formulation of one-stop capacitated hub-and-spoke model as a natural extension of the uncapacitated one-stop model. The model involves arc capacity constraints as well as hub capacity constraints, which enables us to incorporate some practical factors into the model. We also present a branch-and-bound based exact solution method with Lagrangian relaxation bounding strategy, and report some results of numerical experiments using real aviation data. Computational results show the practical significance of the proposed capacitated model.

出版者・発行元：南山大学  

枝とノードの双方に容量制約のあるハブ配置問題を定式化し，この問題の厳密解を求めるラグランジュ緩和法に基づく分枝限定法を構築した．

出版者・発行元：Nanzan University  

ノードとアークの双方に容量制約のあるハブ・アンド・スポークモデルに対して，分枝限定法を用いて厳密解を求める．計算機実験により，容量制約の変化が最適ハブ配置に与える影響が大きいことを示す．

出版者・発行元：The Operations Research Society of Japan  

In this paper, we consider a new competitive hub location model called Stackelberg hub location problem where a big firm and several medium firms compete to maximize their own profit. The big firm first locates a new hub on a plane as a leader on the condition that the other firms locate their new hubs after that. We formulate the leader's problem as a bilevel programming problem with followers' problem as lower level problems, and solve it using SQP method. Computational results show the significance of the proposed competitive hub location model.

出版者・発行元：南山大学  

複数の会社が先手と後手に分かれてハブを配置するシュタッケルベルグ型ハブ配置モデルを提案した．さまざまな状況を考慮して作成したデータを用いて計算機実験を行い，競合のことを考慮せずに配置した場合との利益の差を比較した．その結果，両者の利益には大きな差があることを確認し，競合を考慮することの必要性を示した．

出版者・発行元：日本OR学会  

本報告では，1987年のO'Kellyの論文に始まるハブ選択モデルの研究について，ハブ空港選択モデルを中心に紹介する．

出版者・発行元：南山大学  

出版者・発行元：Pergamon  

We consider the 1-stop multiple allocation p-hub median problem. We formulate the problem as a p-median problem and propose a branch-and-bound algorithm and a greedy type heuristic algorithm. We report computational results for problems with airline passenger interactions between 25 U.S. cities in 1970 evaluated by CAB (Civil Aeronautics Board). For further investigation, we made computational experiments with some random data. The obtained results also show that the proposed algorithms work better than the well-known nested-dual algorithm particularly for relatively small problems.

出版者・発行元：南山大学  

出版者・発行元：Association of Asia-Pacific Operational Research Society  

In this paper, we consider a location problem of relay points in a logistics system. The presented model is more practical compared with the well-known p-hub location model which considers a system of airports. We propose an exact solution method and two heuristic methods for this problem. Computational results of these methods are reported.

出版者・発行元：Center for Management Studies, Nanzan University  

出版者・発行元：南山大学  

出版者・発行元：Center for Management Studies, Nanzan University  

⽇⽐野尋伯(発表者), 佐々⽊美裕

In this paper, we consider a point-to-point based airline network design problem (PPANP) in a competitive environment. In the presented model, we assume that the location of airports and potential OD (origin and destination) demand (i.e., possible passengers in the future) are given, and there is one carrier (existing carrier) in a market that has already set up some ight routes. An entering carrier is planning to establish a given number of point-to-point services (i.e., arcs) simultaneously with the objective of maximizing the total captured potential demand.

In this paper, we consider a robust p-hub median problem where the OD (origin-destination) flow is unknown. The majority of hub location models in the literature assume that all data are deterministic and known; however, the hub location decision should be made from a strategic perspective considering future demand change because it costs a lot of money to change later. From these observations, we apply robust optimization approach to the fundamental p-hub median problem that is the basis of various hub location models proposed in the last three decades. The numerical examples using two data sets including commonly used CAB data set show a rather small impact on the hub network structures.

In this paper, we propose a point-to-point based airline network design problem (PPANP) in which a route connecting two airports is set-up one by one without assuming a hub-and-spoke structure. The proposed model takes into account both carriers' profitability and passengers' perspectives in order to find better airline networks for both carriers and passengers.

クォータ制を導入した大学における授業の教師割り当てを求める問題を0-1整数計画問題として定式化し, 南山大学の授業データを用いて計算実験を行った. その結果, 1クォータ分の教室割り当てを約2秒で求めることができた. 手作業による教室割り当て作業には2 クォータ分で35時間程度を要していることから, 提案するモデルを用いることによって大幅に作業時間を削減できる可能性があることを示した.

品切れ発生と売れ残り発生の最小化を目的として自動販売機コラムへの商品の最適な割り当てを求める問題を整数計画問題として定式化し, 南山大学内に設置されている自動販売機の売り上げデータを用いて計算実験を行った結果について発表した.

We consider a smart community consisting of smart houses in which each is equipped with a fuel cell (FC) system, a photovoltaic (PV) system and a power storage. The supplier of electricity (CEMS: Community Energy Management System) presents the electricity price varying with different time, and customers living in smart houses (HEMS: Home Energy Management System) determine their own optimal levels of buying/selling electricity in responding to the time-varying price. We formulate a problem of finding optimal pricing on the condition that each HEMS finds an optimal schedule to minimize its own total cost as a bilevel programming problem.

We consider p-hub median problems that include demand uncertainty. Using a robust optimization approach, we formulate the problem as a mathematical programming problem that includes second order cone constraints. We show some computational results using CAB data set and with different parameters in order to consider various scenarios.

南山大学の定期試験時間割編成問題を時間割作成, 試験監督割り当て, 教室割り当ての3段階に分け, それぞれモデル化した. また, 定期試験時間割編成を自動で作成するシステムを作成し, 教務課で実際に利用できるユーザインタフェースを開発した. このシステムを使用することにより, 定期試験時間割作成の時間を大幅に短縮することが期待されている.

We consider an airline network design model for passenger transportation based on point-to-point services in which hubs are not necessarily required. We formulate the problem as an integer programming problem and propose a dynamic programming heuristic method to solve large-sized problems. We report some analytical results from passengers’ perspectives.

In this paper, we consider an airline network design model for passenger transportation based on point-to-point services in which hubs are not necessarily required. In the proposed model, the airline network is constructed by opening/closing routes connecting directly between two airports. More precisely,we open a most profitable route one by one, and close a route that is regarded as less profitable at some point after its establishment. We report analytical results from passengers' perspectives.

イベント会場などに併設される大規模な駐車場では, イベント終了後に駐車中の車が一斉に出庫 することが多く, 駐車場内では混雑が発生しやすい. 本研究では, 日本ガイシホール（名古屋市南 区）の駐車場を例として, 駐車場が満車の状態で駐車中の車が一斉に出庫する状況においての混雑 緩和について考える. 日本ガイシホールとは, 主にコンサート等のイベントが定期的に行われてい る収容人数約 1 万人の屋内総合体育施設であり, 2 つの平面自走式駐車場を併設している. 収容台 数はそれぞれ327台と1,385台である．日本ガイシホールの駐車場が混雑している原因は, 駐車場 内の合流点に優先順位を設定してないことであると考え, 駐車場内の道路に優先順位をつけること で駐車場の混雑を緩和できるかどうかをマルチエージェントシミュレーションを用いて検証する.

In this paper, we consider a multi-hop wireless sensor network, where the network topology is given, time division multiple access (TDMA) is employed as medium access control, and all data generated at sensor nodes are delivered to a sink node through the network. For the multi-hop sensor network, we formulate a TDMA scheduling problem as a min-max model in which the objective is to minimize the last transmission time., and a a min-sum model in which the objective is to minimize the sum of the time slot numbers when sensor nodes transmit data. We solve these problems by an optimization software and compare the solutions and their computation times.

We consider a scheduling problem avoiding interference in multi-hop sensor network, where the network topology is given, TDMA (Time Division Multiple Access) is employed as medium access control, and all data generated at sensor nodes are delivered to a sink node through the network. We formulate the problem to find the shortest schedule as a min-max model and a min-sum model. The min-max model yields the shortest schedule. The min-sum model does not guarantee providing the shortest schedule; however, it may give us good schedules over a short amount of computational time, compared to the min-max model. Numerical examples show that the min-sum model can provide good schedules in a reasonable CPU time.

無線センサネットワークを実用化するうえで, センサの電力消費を抑えてネットワークの寿命を延ばすことは重要な課題のひとつである. 本発表では, 干渉が発生しない送信スケジュールを求める問題を整数計画問題として定式化し, すべてのセンサが送信を完了するまでの時間を最小化する送信スケジュールを求める. 対象とするのは, TDMA方式MACプロトコルを用いたマルチホップ型無線センサネットワークであり, ネットワークトポロジは所与とする. 各センサは, ネットワークを介してセンシングしたデータをルートノードにあたる基地局へ送信する. 干渉が発生するとデータ受信に失敗して再送信が必要となり, センサは余分な電力を消費するため, 干渉が発生しないデータ送信スケジュールを求めることは, ネットワークの寿命を延ばすことに大きく貢献する.

In this presentation, we consider an airline network design model based on point-to-point services in which hubs are not necessarily required. In the proposed model, we try to construct an airline network by opening/closing flight legs. More precisely, we open a most profitable leg one by one, which contribute to the increase of the number of customers, and close a leg that has become less profitable at some point after its establishment. We are interested in whether hub-like facilities appear in the resultant network or not, and how different network is established compared with optimal networks of traditional hub-based models. We also analyze the results from the customer’s perspective.

総費用最小化を目的として, 各生産拠点の生産量, および生産拠点と需要点の間の輸送量を多期間に渡って定める自動車組立工場のグローバル生産モデルを提案する. 実データを用いて行った計算実験の結果から, 関税, 生産拠点の生産ライン数の上下限制約, 生産稼働率, 輸出入構成の変化がモデルの解に大きな影響を与えることを示す.

本研究では，路線の開設と廃止を考慮した航空ネットワーク設計モデルを提案する．過去の航空ネットワーク設計モデルの研究では, その多くがハブ空港の設置を前提とし, ハブ空港の配置が与えられるとネットワークの構成が決定するという仮定を設けている．たとえば, ハブ空港間は必ず接続し, ハブ空港以外の空港は1 つ(single allocation rule)または複数(multiple allocation rule)のハブ空港に接続するという仮定である. また, 利用者にとって不便なサービスであっても必ず利用すると暗に仮定したうえで, 航空会社の費用最小化や利益最大化を目的としたものが多い. しかし, 実際には, 乗り換え回数が多い, あるいは極端な遠回りを必要とするなどの不便なサービスは好まれないことを考慮し, 十分な利用者数が見込まれるサービスを提供しなければ, 航空会社が利益を上げるのは難しいと考えるのが自然である. また, 時間の経過とともに利用者数が減少して採算が取れなくなった路線については, 廃止を検討することもある. このように, 時間軸を考慮し, 利用者数の変動によって路線の開設・廃止を決定しながらネットワークを構築する航空ネットワーク設計モデルはあまり研究されていない. 本研究で提案するモデルでは, ハブ空港の設置は前提とせず, 利用者数の増加が見込まれる路線を順次開設し, 採算の取れなくなった路線を廃止することを繰り返すことによって航空ネットワークを構築する. 提案するモデルから得られた最適ネットワークと従来モデルの最適ネットワークを比較して, 利用者の利便性に変化はあるのかどうか, ハブ空港の設置が有効となるのはどのような場合であるのか, 等について分析する.

Electric vehicles (EVs) have been paid much attention as well as other alternative fuel vehicles in this decade as they emit less carbon dioxide. Since the driving range of EVs is limited compared to gasoline vehicles, rapid development of EV battery charging station infrastructures has become a critical issue to increase the dissemination rate of EVs. However, locating sufficient number of charging stations at a time may not be practical due to limited budget. Hence, it would be important to find a well-planned schedule that specifies the location of charging station to be installed in each period over a given time horizon. Kuby and Lim (2005) proposed a flow-refueling location model (FRLM) for alternative-fuel vehicles to find optimal p refueling stations location on a network so as to maximize the total flow volume refueled. In FRLM, it is assumed that vehicle drivers travel between their origin and destination along a pre-determined path, e.g. the shortest path. If charging stations are installed along the path and the distance between any adjacent stations does not exceed the driving range, flows between the two nodes is covered, since the drivers can reach their destination by refueling on their way. Chung and Kwon (2015) considered multi-period planning of FRLM where given number of charging stations are optimally located in each period so as to maximize the total flow covered over the entire planning period. Unlike the previous work by Chung and Kwon (2015), we assume that a flow can be covered if any path between its origin and destination is established, where the level of covered flow is determined by a utility function of travel distance by way of charging stations. In this paper, we consider a scheduling problem to find an optimal order of installing charging stations as well as their locations among candidates with an objective of maximizing the total covered flows over the entire planning period. We propose a greedy heuristic method to find good schedules in reasonable time, and show some results using real data in Tokai region.

We consider a smart community consisting of smart houses in which each is equipped with a fuel cell (FC) system, a photovoltaic (PV) system and a power storage. In the community, the supplier of electricity (CEMS: Community Energy Management System) presents the electricity price varying with different time, and customers living in smart houses (HEMS: Home Energy Management System) determine their own optimal levels of buying/selling electricity in responding to the time-varying price. One of the most important roles of CEMS is to control supply and demand of electricity in the community. Promoting electricity local production for local consumption within the community may lead to achieve a better balance between supply and demand. On the other hand, the objective of HEMS in general is to find an optimal schedule of buying/selling electricity and using the equipment efficiently in order to reduce the total cost required to meet its own electricity and heat demand. We consider a problem of finding optimal pricing to promote local production for local consumption on the condition that each HEMS finds an optimal schedule to minimize its own total cost. We formulate the problem as a bilevel programming problem, where the leader is the CEMS and the followers are HEMSs in the smart community. Computational results show that real-time pricing can effectively control supply and demand of electricity.

Energy consumption in data centers is one of the main concerns of cloud computing. Appropriate aggregation of virtual machines(VMs), which are the computing entities of cloud computing, on limited number of servers in data centers can reduce energy consumption by shutting down the rest of the servers. We present a new formulation of assigning VMs among servers to achieve energy-efficient VM aggregation in cloud data centers. Preliminary results of computational experiments are also shown.

We consider a smart community where the supplier of electricity presents the electricity price varying with different time, and consumers determine their own optimal levels of buying/selling electricity in responding to the time-varying price. We formulate the problem of finding supplier’s optimal pricing as a bilevel programming problem. Computational results show that real-time pricing can effectively control supply and demand of electricity.

One of the main concerns of cloud computing is energy consumption in data centers. Appropriate aggregation of virtual machines(VMs), which are the computing entities of cloud computing, on limited number of physical servers in data centers can reduce energy consumption by shutting down the rest of the servers. We present a new formulation of assigning VMs among physical servers to achieve energy-efficient VM aggregation in cloud data centers.

In this presentation, we show some mathematical properties of new indices for evaluating spatial demand-and-supply balance. More precisely, we show that the sequence of solutions generated by the iterative algorithm converges to the proposed indices. We also discuss the relationship between the solutions and those obtained by solving a mathematical programming problem with an objective of minimizing the variance of indices. The objective corresponds to minimize unfairness among customers.

In this paper, we consider a scheduling problem of locating EV battery charging stations where the location of all stations to be installed eventually is given. Due to budgetary limitation, it might be generally difficult to install all stations at a time. In such a case, the stations would be located in order according to a pre-determined schedule. We propose a greedy heuristic method to find good schedules in reasonable time, and show some results using real data in Tokai region.

This paper considers a strip packing problem with rectangles that are flexible in their dimensions, but fixed in their area. We generalize the best-fit heuristic, a well-known algorithm to solve the strip packing problem for rectangles of fixed sizes, investigating a set of simple heuristic rules with some modifications of the original rules. We also propose data structures to improve the efficiency of the resulting algorithms. The obtained solutions are evaluated on a set of 22; 500 randomly generated instances. Our approach provides good solutions, with an occupation ratio of more than 96% on average, for instances with flexible rectangles.

The variety of models are proposed and analyzed in order to evaluate the quality of public services with an objective of providing better services in the facility location literature. Ukai and Sasaki proposed new indices for evaluating spatial demand-and-supply balance. They also proposed an iterative method to obtain the indices by virtually allocating supply capacity of each facility to each customer located within a certain distance. Some numerical results are presented on maps, where the number of hospital beds and the population in Kanagawa Prefecture are used as supply and demand, respectively. In this paper, we show some mathematical properties of the proposed new indices. More precisely, we show that the sequence of solutions generated by the proposed iterative algorithm converges to a solution. We also discuss the relationship between the solutions and those obtained by solving a mathematical programming problem with an objective of minimizing the variance of indices. The objective corresponds to minimize unfairness among customers

Public services such as ambulance service and nursery care service are required to serve as equitably and efficiently as possible. To evaluate fairness, efficiency and sufficiency of the provided public services in target community, supply quantity per capita and/or per unit area can be simply used. This method is straightforward and easy to understand; however, the results largely depend on the size of each divided region. Ukai and Sasaki proposed new indices for evaluating spatial demand-and-supply balance and an iterative method to obtain the indicies. In addition, they showed some numerical results on maps, where the number of hospital beds and the population in Kanagawa Prefecutre are used as supply and demand, respectively. In this presentation, we show some mathematical properties of the proposed new indices. More precisely, we show that the sequence of solutions generated by the proposed iterative algorithm converges to a solution. We also discuss the relationship between the solutions and those obtained by solving a mathematical programming problem with an objective of minimizing the variance of indices.

Recent years, in Japan supply insufficiency of medical service becomes important issue caused by aging society. Public services such as ambulance service are required to serve as equitably and efficiently as possible. For measuring or comparing sufficiency of service, supply quantity per capita and/or per area is generally used. This kind of indices is suitable for regions which are large enough to be considered as uniform density. In this paper, we propose an index representing supply-and-demand gap, which is generalization of supply sufficiency above. Then, we discuss features of proposed index considering numerical examples and iterative procedure how to calculate it. Finally, we adapt it to numbers of beds of acute hospitals in Kanagawa Prefecture, and visualize it.

In this paper, we consider a scheduling problem of locating EV battery charging stations where the location of all stations is given. Due to budgetary limitation, it might be generally difficult to locate all stations at a time. In such a case, the stations would be located in order according to a pre-determined schedule. We show how the schedule difference give an impact on user convenience, and propose heuristics to find good schedules.

In this presentation, we calculate sickbed supply-demand balance proposed by Ukai and Sasaki, and visualize it on maps. As a target, we focus on acute medical providing system in Kanagawa prefecture, Japan. Supply quantity is the number of sickbed of medical institutes, and demand quantity is population of small section. Index of supply-demand balance has a dimension of sickbeds per capita. As a calculation result, some sub-regions in which the supply-demand balance values are the same appears in the object region. These sub-regions are different from the medical administration areas currently setup by the local government.

We consider a problem on a network to find the best location of facilities among given candidate sites where every demand node is covered by at least one of the facilities, and facility-level network is connected. The objective is to minimize the total travel distance between each demand node (OD: origin and destination) pair.

We consider a strip packing problem with rectangles that are flexible in their dimensions, but fixed in their area. Using an adaptation of the best-fit heuristic, we investigate a set of simple heuristic rules with some improvements and evaluate the quality of the solutions on a set of randomely generated instances. Our approach provides good solutions for instances with flexible rectangles.

In recent years, some regions in Japan have been faced with a severe shortage of medical resources while some others have enough capacity. The size of such imbalances are different in each medical district or type of disease, and directly affects the accessibility for patients to hospitals. One of the major reasons that causes these imbalances is a mismatch between supply and demand. In this paper, we propose mathematical models for reallocating resources so as to reduce accessibility imbalance.

In this paper, we consider an examination timetabling problem that commonly arises in universities, where all examinations are assigned to one of the given number of time slots satisfying room capacity constraints, avoiding students taking more than one examination at the same time. Specifically, the proposed model generates a timetable in which each examination is assigned to the same time slot as regular class schedule as much as possible to provide more convenience to students, which also contributes to reduce the number of examinations scheduled on Saturday or fifthe periods. We solve the problem using IBM ILOG CPLEX to obtain an optimal timetable and then apply a local search algorithm to find better room assignments. The computational experiments using the data provided by Nanzan University show the proposed approach generates a better schedule including the assignments of examination supervisors, and drastically reduces the time required for preparing the examination timetable.

We consider network design for a low-cost air carrier (LCC) entering a market where mega carriers have already provided flight services. We assume that the level of captured passengers by LCC in each OD pair is determined by a logit function in which the utility is defined with the price and the frequency of flights provided by each carrier. Using the real data reported by Japan’s Government, we estimate the parameters of the logit model. The proposed network design model finds an optimal hub-and-spoke network for LCC and the flight frequency in each air route simultaneously.

We consider two hospital location models where the numbers of inpatients of four major diseases (respiratory, circulatory, digestive and musculoskeletal diseases) and a limited number of beds provided by hospital departments to treat the diseases are taken into account. In general, the market share of hospitals can be described by the gravity model, which suggests that distance to hospital is an important factor for patients. Hence the objective of the presented models is minimizing the total travel distance to hospitals for patients. In the first model, we focus on locating a special hospital providing treatment for one of the four diseases. In the second model, we consider optimal locations of general hospitals with all the four departments under the assumption that all inpatients can be admitted to hospitals located within a certain distance of their home. Our primal goal is to see supply demand mismatch in the health-care services, and derive a new direction to improve accessibility for patients. We will show the numerical examples using real data in Shonan West Region and Kenoh Region in Kanagawa Prefecture.

Due to coming super-aged society in Japan, the distribution of patients affected by acute and chronic disease has been changed drastically. Since the current healthcare system was designed in several decades ago without taking account of facing aged-society, many of medical staff are concerned about collapse of the healthcare system in the near future. We are trying to reallocate resources to improve the quality of healthcare services using operations research technique.

In this study, we propose a facility location model for EV charging stations in which all demand nodes are connected to allow potential drivers to travel between any demand points by EVs in a given area. Objective is minimizing the total travel distance so that we expect to provide better routes for the drivers. We formulate the problem as a multi-commodity flow problem, where a commodity corresponds to a flow from an origin to a destination. We solve the problem using IBM ILOG CPLEX, and present optimal locations of EV charging stations in the Tokai region (Aichi, Gifu, Mie and Shizuoka Prefectures).

We consider a multi-hop sensor network, where the network topology is a tree, TDMA is employed as medium access control, and all data generated at sensor nodes are delivered to a sink node through the network. For the multi-hop sensor network, we formulate a scheduling problem as a min-max model, where the objective is to minimize the latest transmission time, and as a min-sum model, where the objective is to minimize the sum of the time slot numbers. We then attempt to solve those problems by an optimization software and examine computational times to solve them.

In this paper, we consider the design of airline network in Asia where optimal locations of the gateways and local hubs are established. We report some results using the demand data reported by IATA in 2005. The results show interesting features of gateway locations in Asia.

In this paper, we consider the design of large-scale hub-and-spoke transportation networks in a competitive environment. We adopt the hub arc location model that locates arcs with discounted transport costs connecting pairs of hub facilities. Two firms compete for passengers in a Stackelberg framework where the leader firm locates hub arcs to maximize its revenue, given that the follower firm will subsequently locate its own hub arcs to maximize its own revenue. Several mechanisms are presented to allocate traffc between the two firms based on the relative attractiveness of travel via the competing hub networks. Results with up to three hub arcs for each competing firm show the role of a competitive environment in designing transportation systems.

点容量付き内向木詰込問題とは，有向グラフ，根，点容量関数，枝消費関数が与えられたとき，根付き全域内向木をいくつ詰め込めるかを扱う．枝消費関数によって根付き全域内向木の各点における消費が決まる．制約は，各点において，根付き内向木の消費の合計が点容量を超えないことである．この問題は，センサーネットワークの研究における最も重要な問題である，ネットワークライフタイム問題の１つである．本研究では，グラフが非巡回的な場合，消費関数が距離に依存する場合，などにおける点容量付き内向木詰込問題の計算複雑度を明らかにする．

点容量付き内向木詰込問題のいくつかの場合に関して，その計算量を明らかにする．とくに，出力消費が距離に依存する場合に弱NP 困難であることを示す．

本発表では，昨年発表したモデルに改良を加え，発表プログラム自動作成にかかる時間を大幅に短縮した結果について報告する．発表プログラム作成問題 を4段階の問題に分け，それぞれ0-1整数計画問題として定式化し，最適化ソフトウェアOPL-CPLEXを用いて解を求めるプログラムを作成 した．2006年度に開催されたOR学会研究発表会の実データを用いて発表プログラムを作成した結果についても紹介する．

In this paper, we consider the following two problems in a continuous plane related to wireless sensor using the Voronoi diagram. We assume that the sensing range of each sensor should be a disk with the same radius, and the sensors are distributed randomly in a unit square. The first problem is to find the number of sensors which is needed to cover the sensing area. For this problem, we need to calculate the area covered by many disks whose centers are randomly distributed in a square. The second problem is to decide the minimum radius of the sensing range of the sensors to cover the whole sensing area when the sensors can move with a given small distance.

OR学会研究発表会の発表プログラムは、これまで実行委員の手作業で作成されていた．本研究では，発表プログラム作成問題を3段階の問題に分け，それぞれ0-1整数計画問題として定式化する．さらに，最適化ソフトウェアOPL-CPLEXを用いて解を求めるプログラムを作成し，発表プログラム作成にかかる作業時間の大幅な短縮をはかった．2006年度に開催されたOR学会研究発表会の実データを用いて発表プログラムを作成した結果についても紹介する．

最短経路数え上げ問題は，これまでに理論的研究を中心に進められ，いくつかの興味深い結果が得られている．本研究では，道路交通容量を考慮し，最短距離経路ではなく最短時間経路を数え上げることにより渋滞の分析を試みる．名古屋市内の実道路データを用いて計算機実験を行った結果，橋の付近から渋滞が発生するという興味深い結果が得られた．

We consider the gateway airport location problem, where the gateway and several local hubs are selected among candidate airports. We show numerical examples using real flight demand data evaluated by IATA in 2005 to find out which airports are advantageous to be served as the gateway and local hubs in Asia in terms of travel distances for passengers.

The most crucial factor of the sensor network is limited power of the built-in battery. So, we need a good management of the sensor network to save the batteries. In this point of view, topology construction is important. In this talk, we show that the cluster-based topology construction problem can be formulated as an uncapacitated facility location problem, which brings us a significant improvement in terms of the network life time. We also show some variations of the formulation and numerical examples.

近年の国内航空需要の増加に伴い, 航空と鉄道の競争はますます激しくなっている. 本研究では, 旅行者は旅行時間によって移動手段を選択するものと仮定し, 鉄道との競合を考慮した航空路線の再編成を行うモデルを提案する. 国土交通省が提供している交通機関別都道府県間流動表のデータを用いて行った計算結果について報告する.

瀬戸市では, 現在, 資源ごみ回収ルートを定めていない. そこで, 本研究では, 回収の効率化を目的として, 移動距離が最小となる回収ルートを求める. 国土地理院が発行している数値地図25000の道路データをもとに作成した道路ネットワークを用い, 回収車の積載容量および道路の幅(車線数)を考慮し, 回収車ごとの詳細な回収ルート求める.

We present a new model to find the optimal gateway airport in a region. To establish a suitable airline network in a region such as Asia, we should take into account the interregional demand, i.e. the number of outgoing and inbound passengers from/to the region. The problem can be regarded as a hierarchical location problem. We show numerical results of the Asian gateway airport using OD data between Asia and Europe or North America evaluated by IATA in 2005.

階層型施設配置モデルの1つであるミニマックス型MLTPがp-センター問題に帰着することを利用したミニマックス型FTPLPの解法を提案し，施設の数が1の場合の最適解を求める．

マルチホップ型センサネットワークにおいて，データ送受信の際に発生する干渉を考慮し，センサがモニタしたデータを効率よく基地局まで送信するスケジュールを求めるモデルを提案する．また，最適化ソフトウェアを用いて計算した結果について報告する．

Most of the topology constructions for wireless sensor networks studied so far are based on a myopic view, where the topology construction is carried out round-by-round. In this research, we take power consumption of sensors over multiple rounds into account, and formulate the problem as a multi-dimensional knapsack problem. We also propose a solution method to maximize the network lifetime. The computational experiments show that the proposed approach provides efficient topology construction.

最短経路数え上げ問題はこれまで理論的な研究が中心に行われてきた．そこで，応用例として，重み付き最短経路数え上げ問題を用いて渋滞予測を行うことを試みる．本発表では，名古屋市内の全町丁目の人口データに重力モデルを適用して作成したODデータを用い，名古屋市道路ネットワーク上で重み付きの最短経路数え上げを行った結果について発表する．

One of important issues in wireless sensor networks is how to extend the network lifetime. For this purpose, various routing topologies and related approaches have been studied. We consider a routing problem which arises in wireless sensor networks based on a multi-hop topology. We formulate the problem as a multi-dimensional knapsack problem and solve 100-nodes test problems in order to nd optimal routings. The computational experiments show that the proposed approach produces efcient routing

From a view of facility location theory, we can consider that LEACH-C, which is one of the principal studies on cluster-based network organization, formulates the clustering problem as a p-median problem. We point out drawbacks of the formulation in LEACH-C. To overcome the drawbacks, we formulate the problem as an uncapacitated facility location problem. Computational experiments show that the proposed algorithm can extend the lifetime of sensor networks.

階層数を固定しないツリー(クラスタツリー)を用いたセンサネットワークの構成方法を提案する．数値実験により，従来の2階層のクラスタ型センサネットワークと比較して実行ラウンド数が約2倍になることを示す．

We presented an Asian hub-and-spoke model and reported numerical examples using real origin-destination demand data evaluated in 2005 by IATA.

センサネットワークにおけるクラスタヘッドの選択問題を容量制約なし施設配置問題として考えることにより，クラスタリング手法の改良を行う．計算機実験の結果，提案する手法を用いると従来の手法よりもセンサネットワークの寿命が長くなることが確認できた．

対象地域から特定の別の地域への航空需要を考慮したゲートウェイ空港最適配置モデルを提案し，都市の人口データをもとに作成したテストデータを用いて数値実験を行った結果を紹介した．

We consider hierarchical location problems called MLTP and FTPLP, where q facilities and p transfer points are located on a network and each customer goes to one of the facilities directly or via one of the transfer points. Although good heuristics have been proposed for the minisum MLTP and FTPLP, no exact optimal solution has been computed due to the size of the problems. We present new formulations to solve the minisum version of the problems exactly.

FTPLP is one of the hierarchical facility location problems. We propose a heuristic algorithm based on a network Voronoi diagram to solve the minimax version as well as the minisum version of FTPLP. The network Voronoi diagram is a network version of the Voronoi diagram, which plays important roles in solving various network problems. Computational results using the benchmark data set for p-median problems provided by OR-Library show that our algorithm efficiently solves FTPLP and its variations

We propose a new heuristic algorithm for sensor netwroking problems. When many small wireless sensors are scattered in a region, the problem is to construct a virtual netwrok of these sensors so as to monitor the region as long as possible. The critical resource of the sensor netwrok is the duration of the batteries of the sensors. We formulate the problem as a mixed integer programming problem and solve it by a heuristic method using the netwrok Voronoi diagram.

In the Asia-Pacific region, huge airports have been constructed in this decade. These airports struggle fiercely one another in order to serve themselves as the gateway of the Asia-Pacific region. We address this issue with a mathematical programming approach, where the location of exact optimal gateway hub airport and several local hub airports in the Asia Pacific region are determined with the objective of minimizing the total transportation cost.

階層型施設配置モデルMLTPとFTPLPに対して，新しい定式化を提案した．これまでは，問題の規模が大きいために厳密解は求められなかったが，提案する定式化を用いて求めることができた．

OR/MS methodology was applied to the management of the Nanzan School complex. The administration recognized OR/MS as a strong effective management tool, This report delas with how the school complex change so that it can survive the increasing competition among institutions of higher education.

We consider a competitive hub arc location model and formulate it as a bilevel programming problem. We solve the problem by using a smart enumeration method and branch-and-bound method to obtain exact optimal solutions. From the numerical results using CAB data, we found our smart enumeration method gave us good results in terms of computational time.

We extend the hub arc location model to incorporate the competitive environment in which rival firms "locate" their services. We consider a case, where two competitors locate their own hub arcs -- which translates to the decision on which of their routes should flow be consolidated with larger, fuel-efficient aircraft flying on these "consolidation routes".

In this paper, we consider an airline network design model in a competitive environment, where the companies are allowed to　not to have any hubs. In the other words, the companies are allow to establish legs between any cities without intermediate stops. Our objective is to see how the services through hubs or the non-stop services work within the airline network structure.

競合を考慮した容量下限制約付ハブ・アーク配置モデルの紹介し，計算機実験の結果を示した．さらに，今後のモデルおよび解法の改良の可能性について発表した．

In this talk, we proposed a new hub network design model based on the Stackelberg hub location model.To avoid the possibility of unprofitable services, we incorporated flow threshold constraints into the model. The main objective is to make it clear how the network structure can be affected by the flow threshold constraints and the competitor's strategies.

We consider a statistical approach to decide the spec of the center console of automobiles. The design of the center console by trial and errors usually consumes lots of time. If we knew the relationships between the usability and the physical spec of the dials and switches, we might be able to shorten the decision process. In order to obtain insights about the relationships, we carry out a questionnaire survey to 12 samples of center consoles of automobiles.

In this talk, we extend the hub arc location model to incorporate the competitive environment in which rival firms "locate" their services. We consider a case, where two competitors locate their own hub arcs -- which translates to the decision on which of their routes should include larger, fuel-efficient aircraft flying on their "consolidation routes". The objective here is to maximize their own profit. We show how these problems can be formulated as integer programs.

競合を考慮したハブ配置モデルとしてシュタッケルベルグ・ハブ配置モデル(SHLP)およびその計算実験結果を紹介し，このモデルの改良点を明らかにした. 改良モデルとして，ハブ・ネットワーク設計モデル(HNDP)を構築し，計算実験の結果を示した．

ハブ・アンド・スポークモデルに関するこれまでの研究を概観したあと, 特に1-stopモデルを用いて, 制約条件や競合相手の戦略の変化によるハブの最適配置やネットワークの構成の変化について分析した結果を発表した．さらに, 分析結果をもとに, 実用性を重視したモデル構築に必要な要因について言及した．

競合する2社が先手と後手に分かれてハブを配置し，それぞれ自社のネットワーク設計を行う競合型ハブ・ネットワークデザイン問題を新しく提案し，2段階最適化問題として定式化した．

容量制約付きハブ配置問題において，容量制約の変化がハブの最適配置および総費用に与える影響を分析した結果について報告した．

One-stop hub location model に関する研究ついて概観した．これまでの多くの研究で対象とされてきたtwo-stop modelとの相違点を説明し，このモデルクラスに属する基本モデル，容量制約付きモデル，競合を考慮したモデルについて，計算機実験の結果を交えながら解説した．

容量制約のあるハブ配置問題の厳密解を求める分枝限定法について，下界値計算と分枝方法の改良を行い，新たに提案した．計算機実験の結果から，枝の容量制約の変化が最適解に及ぼす影響は特に規模の大きいネットワークで大きくなることが確認できたことを報告した．また，容量制約が変化しても常にハブとして選択される頑健なハブの存在も明らかになり，このような頑健性を考慮したハブ配置問題を考える必要性について述べた．

1-stop容量制約付ハブ配置モデルの定式化，解法，計算機実験の結果について発表した．

過去に提案された競合型ハブ配置モデルを紹介し，新たに複数の会社が先手と後手に分かれてハブを配置するシュタッケルベルグ型ハブ配置モデルを提案した．競合のことを考慮せずに配置した場合との利益の差を比較し，競合を考慮することの必要性を示した．

We present a Stackelberg hub location problem in which a leader firm and two follower firms compete each other to maximize their own profit. First the leader firm locates a hub on a plane on the condition that the follower firms locate their hubs after that. We formulate the problem as a bilevel proprogramming problem and solve it using SQP method. Computational results show the validity of the proposed competitive hub location model.

「ORを用いた救命救急医療体制の最適化の試み」(井上茂亮氏＠東海大学と共同講演), 第13回 サービスサイエンス研究部会（筑波大学にて開催）．

「アジアにおける航空ネットワークの変化」，日本OR学会第64回シンポジウム（コラッセふくしまにて開催）にて講演．

「アジアにおけるゲートウェイ空港の最適配置モデル」，
東北大学経済学研究科主催 応用統計計量ワークショップにて講演．

「アジアにおけるゲートウェイ空港の最適配置モデル」，
日本OR学会「政治と社会と行政のOR」研究グループ第10回研究会にて講演．

「競合を考慮した航空ネットワーク設計モデル」(James F. Campbell, Andreas T. Ernst and Mohan Krishnamoorthy との共同研究)，
南山大学数理情報研究科・数理情報研究センター オープン・リサーチ・センター「都市の持続可能な繁栄のためのインフラストラクチャーの最適運用計画の策定と普及」 2009年度第3回公開研究会「航空輸送におけるネットワーク設計」にて講演．

「オペレーションズ・リサーチの紹介-モデリング手法と応用例」，
Washington University in St. Louis の医学部で開催されたJapanese Happy Hour (セントルイス在住日本人研究者の会)にて講演。医学分野での応用例を交えてORの紹介を行った．

University of Missouri - St. Louis に Visiting Professor として滞在．

California State University - Fullerton に Visiting Scholar として滞在．

「センサネットワーク構築と最適化問題」，第19回RAMPシンポジウム(日本OR学会常設研究部会数理計画主催)にて講演．センサネットワーク構築に関連して発生するさまざまな問題を最適化問題としてモデル化できることを紹介し，この分野における最適化手法の適用の可能性について述べた．

「ソルバを用いたOR的解析手法の紹介」，会津大学「課外プロジェクト」．

「OR的思考のすすめ-さまざまな分野で応用されるORの事例-」，SAM (日本経営近代化協会) 10月例会．

共同研究のため，CSIRO Mathematical and Information Sciences (Clayton, Australia) に滞在．

共同研究のため，CSIRO Mathematical and Information Sciences (Clayton, Australia) に滞在．

山之内亮介: 日本オペレーションズ・リサーチ学会 2014年度学生論文賞, 論文題目「連結制約と被覆制約を持つ施設配置問題に対する発見的解法」, 2014年8月28日受賞.

小野内雄一: 第41回日本オペレーションズ・リサーチ学会中部支部研究発表会 学生論文賞優秀賞, 論文題目「大学の定期試験時間割編成システムの試作」, 2014年3月15日受賞.

・数学演習I・II
単に定義や定理を数式のまま丸暗記するのではなく，きちんと理解する姿勢をつけるために，できる限り図を用いてわかりやすく説明した．さらに，反復して学習することが必要な箇所については，授業中に適宜復習の時間を設け，学生同士で相談して答えを導き出すよう促すなど，参加型の授業を試み，理解の補助となるようにした．
・「OR概論I」
この授業ではじめてオペレーションズ・リサーチ(OR)を学ぶ学生が多いので，問題の解法よりも，身近なところでORがどのように役に立っているかについて具体例をあげて解説することからはじめた．線形計画法やスケジュール問題の基本的な問題については，授業中に例題の解説をしたあと小レポートを行い，理解度を確認しながら授業を進めた．